Optiver·Data Scientist·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Optiver Data Scientist interview with a math-heavy algorithmic problem that looks deceptively like a simulation exercise but punishes you hard if you actually try to simulate it. The whole thing hinges on recognizing a number theory pattern fast enough to implement something logarithmic.

Questions Asked (1)

You have two non-empty piles of stones with sizes a and b. Each move, you double the smaller pile by transferring that many stones from the larger one. Determine whether this process will eventually empty one of the piles, or cycle forever. Your solution must run in logarithmic time.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was just to simulate it and slap a visited-states check on top.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the process as a state transition on the pair (a, b) and identify an invariant that determines termination. Use the binary representation of the ratio a/b to derive a logarithmic-time condition, likely involving the continued fraction expansion or the Euclidean algorithm.

Pro tip: Connect the problem to the Euclidean algorithm: the number of moves until termination is related to the sum of partial quotients in the continued fraction of a/b. This shows logarithmic time because the Euclidean algorithm runs in O(log min(a,b)).

1. Understand the move and termination condition

Clarify that each move doubles the smaller pile and subtracts that amount from the larger. The process stops when one pile becomes zero; otherwise it may cycle.

2. Identify invariants and patterns

Observe that the total number of stones is invariant. Also, the ratio of the two piles changes in a predictable way: if a < b, the new pair is (2a, b-a).

3. Relate to Euclidean algorithm

Show that the sequence of moves mimics the subtractive Euclidean algorithm on the pair (a, b). The number of moves until termination equals the sum of the quotients in the continued fraction of a/b.

4. Derive logarithmic-time condition

Use the fact that the Euclidean algorithm runs in O(log min(a,b)) steps. Therefore, we can simulate the process efficiently by jumping multiple moves at once using division.

5. Implement and verify

Write a function that repeatedly applies the transformation using modulo arithmetic to skip redundant steps, and check if it terminates. Test with small examples to confirm correctness.

Key Points to Mention

Invariant: total stones a+b remains constant.
The process is equivalent to the subtractive Euclidean algorithm.
Termination occurs if and only if the ratio a/b is rational (which it always is for integers), but cycles can occur if the process is not exactly Euclidean? Actually, for integers, it always terminates? Wait, need to check: The problem says 'determine whether this process will eventually empty one of the piles, or cycle forever.' For integer piles, does it always terminate? Let's test: a=1, b=2 -> move: smaller=1, larger=2 -> double smaller to 2, subtract 1 from larger -> (2,1) -> then smaller=1, larger=2 -> double smaller to 2, subtract 1 from larger -> (2,1) again? Wait: (1,2): smaller=1, larger=2. Transfer 1 from larger to smaller: smaller becomes 2, larger becomes 1 -> (2,1). Then smaller=1, larger=2 -> transfer 1 from larger to smaller: smaller becomes 2, larger becomes 1 -> (2,1) again. So it cycles! So not always terminate. So condition for termination? It terminates if at some point the larger is exactly twice the smaller? Actually, if larger = 2*smaller, then doubling smaller makes it equal to larger, and subtracting that amount from larger makes larger zero. So termination occurs when the ratio is 2:1. Otherwise, it may cycle. So the process is not exactly Euclidean. Need to analyze carefully. The problem is known: it's related to the binary Euclidean algorithm? Actually, the move is: if a < b, then (a,b) -> (2a, b-a). This is similar to the transformation in the binary GCD algorithm. The process terminates if and only if a/b is a power of 2? Let's test: a=1, b=3: (1,3) -> (2,2) -> then smaller=2, larger=2? But they are equal? The problem says two non-empty piles, each move double the smaller by transferring from larger. If equal, which is smaller? Probably if equal, then doubling one would require transferring from the other, but then the other becomes zero? Actually, if a=b, then smaller is a (or b), larger is b (or a). Transfer a from larger to smaller: smaller becomes 2a, larger becomes 0. So it terminates. So (2,2) terminates. So (1,3) terminates. So not only powers of 2. Let's test (1,4): (1,4)->(2,3)->(4,1)->(3,2)->(1,4)? Wait: (1,4): smaller=1, larger=4 -> (2,3). (2,3): smaller=2, larger=3 -> (4,1). (4,1): smaller=1, larger=4 -> (2,3) again? Actually (4,1): smaller=1, larger=4 -> double smaller to 2, subtract 1 from larger -> (2,3). So cycle: (1,4)->(2,3)->(4,1)->(2,3)... So cycles. So condition for termination? It seems termination occurs if and only if the ratio a/b is a rational number whose continued fraction has all partial quotients equal to 1? Not sure. Actually, the process is equivalent to the map on the ratio r = a/b. If r < 1, then new ratio r' = 2r/(1-r). If r > 1, then r' = (r-1)/(2). This is a Möbius transformation. The process terminates if the orbit hits 1 (since then next move makes one zero). So we need to determine if the orbit of r under this map ever hits 1. This is related to the binary expansion of r. In fact, the map is conjugate to the doubling map on the circle. So termination occurs if and only if r is a rational number with denominator a power of 2? Let's test: r=1/3 terminates? (1,3) -> (2,2) -> terminates. r=1/3 is not a power of 2 denominator. So that's not it. Actually, the map is: if r<1, r' = 2r/(1-r). If r>1, r' = (r-1)/2. This is the same as the map on the binary expansion? Consider r = a/b. The process is exactly the binary Euclidean algorithm? Actually, it's known as the 'stone game' or 'Euclid's algorithm with doubling'. The termination condition is that the ratio a/b is a rational number whose continued fraction expansion has all partial quotients equal to 1? Let's test: 1/3 = [0;3] -> not all 1. But it terminates. So no. Let's analyze: The process terminates if at some point the two piles are equal. That means a=b. So we need to know if the orbit of (a,b) under the map ever reaches a state where a=b. The map is invertible? The inverse of (a,b) -> (2a, b-a) when a<b is: given (x,y) with x>y? Actually, the forward map: if a<b, (a,b)->(2a, b-a). If a>b, (a,b)->(a-b, 2b). So it's symmetric. The condition for termination is that the ratio a/b is a rational number that can be reduced to 1 by repeatedly applying the map. This is equivalent to saying that the binary expansion of a/b is eventually periodic? Actually, the map is conjugate to the shift map on the binary expansion. Specifically, consider the fraction a/(a+b). Then the move corresponds to doubling modulo 1. Let's see: Let x = a/(a+b). Then if a<b, new a' = 2a, new b' = b-a, so new sum = a+b. New x' = 2a/(a+b) = 2x. If a>b, new a' = a-b, new b' = 2b, so new x' = (a-b)/(a+b) = 2x - 1. So in both cases, x' = 2x mod 1. So the process is exactly the doubling map on the unit interval. Termination occurs when a=0 or b=0, which corresponds to x=0 or x=1. But x=0 means a=0, not allowed initially. x=1 means b=0. So termination occurs when the orbit of x under doubling mod 1 hits 0 or 1. Since x is rational, its orbit is eventually periodic. It hits 0 if and only if x is a dyadic rational (denominator power of 2). But wait, x=1/3 gives a=1, b=2? Actually, if a=1, b=3, then x=1/4, which is dyadic. So it terminates. If a=1, b=4, x=1/5, not dyadic, so it cycles. So termination occurs if and only if a/(a+b) is a dyadic rational, i.e., a/(a+b) = k/2^n for some integers k,n. Equivalently, a+b is a power of 2 times something? Actually

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