Optiver·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Optiver Data Scientist interview had a math/logic puzzle that looked deceptively simple on the surface. One coding question about pile balancing, and it required actually thinking through the structure of the problem rather than just throwing a loop at it.

Questions Asked (1)

You have two piles of apples with sizes a and b. In each move, you pick one pile as the receiver and double it by moving apples from the other pile (only legal if the giving pile has enough). Can you reach a state where both piles are equal? Return true or false.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Spent the first few minutes trying to simulate it with a BFS and realized that could blow up badly given the constraint range goes up to 10^9.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases (e.g., zero piles, negative sizes). Then, derive the necessary and sufficient condition for equality by analyzing the invariant: the total sum must be even, and the smaller pile must be able to grow to half the sum via a sequence of doublings. Finally, implement a simple check (e.g., using GCD or bitwise operations) and discuss time/space complexity.

Pro tip: Mention that this problem reduces to checking if the smaller pile can be doubled repeatedly to reach half the total, which is equivalent to the smaller pile dividing the larger pile's difference in a specific way. This shows you can spot mathematical structure quickly.

1. Clarify constraints and edge cases

Ask about input ranges, whether piles can be zero, and if negative sizes are allowed. Confirm that moves are only legal when the giving pile has enough apples.

2. Identify necessary conditions

The total sum must be even, and the smaller pile must be less than or equal to half the sum. If not, equality is impossible.

3. Derive the invariant

Observe that each move doubles the receiver and subtracts from the giver, preserving the total sum. The key is whether the smaller pile can be doubled enough times to reach half the sum without exceeding it.

4. Reduce to a simple check

Show that the condition is equivalent to: let s = min(a,b), l = max(a,b). Then equality is possible iff (s + l) is even and s can be doubled to (s+l)/2, which simplifies to checking if l is a multiple of s and the quotient is a power of two.

5. Implement and analyze

Write a function that checks the condition in O(1) time using bitwise operations or division. Discuss time and space complexity, and test with examples.

Key Points to Mention

Total sum must be even.
The smaller pile must be able to reach half the sum via doublings.
The condition reduces to checking if the larger pile is a multiple of the smaller pile and the quotient is a power of two.
Edge cases: zero piles, equal piles initially, and very large numbers.
Time complexity O(1) and space O(1).
Alternative approach: simulate moves with a while loop, but note it may be inefficient for large inputs.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.