Optiver·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Optiver quant engineer interview threw a classic probabilistic puzzle at me, framed as a Markov chain problem. Pretty standard for this kind of role but the execution under pressure is where things get tricky.

Questions Asked (1)

Two ants start at opposite vertices of a regular octagon. Each step, both flip a fair coin and move one edge clockwise or counterclockwise. What is the expected number of flips until they meet at the same vertex or cross on the same edge? You should model this as a Markov chain on the distance between the ants.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The hint to use a Markov chain on the gap between them is really what unlocks it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the distance between the ants as a Markov chain on the number of edges along the shorter arc (0 to 4). Set up equations for the expected hitting time from each state, considering that the distance changes by -2, 0, or +2 with certain probabilities, and solve for the initial state (distance 4).

Pro tip: Clearly define the state space and transition probabilities, and note that the distance changes by 0 or ±2, so the chain is periodic; this simplifies the equations and avoids common mistakes.

1. Define the state space

Identify the distance between ants as the number of edges along the shorter arc, ranging from 0 to 4. State 0 represents meeting at a vertex, and state 4 is the initial state (opposite vertices).

2. Determine transition probabilities

For each state, compute the probabilities of moving to other states based on the four possible coin flip outcomes. Note that the distance changes by -2, 0, or +2, and the chain is periodic.

3. Set up expected hitting time equations

Let E_i be the expected number of flips to reach state 0 from state i. Write equations: E_0 = 0, and for i > 0, E_i = 1 + sum_j P_{i,j} E_j.

4. Solve the system of equations

Solve the linear equations for E_1, E_2, E_3, E_4. Use substitution or matrix methods, and verify the solution by checking boundary conditions.

5. Interpret the result

The value E_4 is the expected number of flips until the ants meet or cross. Present the final answer clearly and explain its significance.

Key Points to Mention

State space reduction using symmetry: distance along shorter arc (0 to 4).
Transition probabilities: from distance d, possible new distances are d-2, d, d+2 with probabilities depending on d.
Periodicity of the chain: distance changes by even numbers, so states split into two communicating classes.
Expected hitting time equations: E_i = 1 + sum P_{i,j} E_j for i > 0, with E_0 = 0.
Solving linear equations: use substitution or matrix inversion to find E_4.
Final answer: expected number of flips is 8 (or the computed value).

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