10-Node Graph Expected Traversal

This quant interview question is about modeling a random traversal on a fully connected graph and understanding how long it takes, on average, to see every state at least once. It reframes a classic probability puzzle in the language of graphs, which is common in quantitative finance interviews and modern quant prep material. The setting forces you to recognize a familiar stochastic structure behind a seemingly new context.

It trains your grasp of expected value in discrete-time stochastic processes and your ability to map graph problems to probabilistic frameworks. You practice reasoning about independence, repeated sampling, and how expectations add across stages of a process. It also builds comfort turning an abstract description of a random walk into a clean mathematical model.

This matters for quant interviews because many pricing, risk, and simulation tasks boil down to understanding sampling, convergence, and coverage of states or scenarios. Interviewers use this style of question to test whether you can see through surface complexity, identify the core probabilistic mechanism, and reason quantitatively about time-to-completion in random processes. It is a strong filter for candidates who have done serious quant prep and can connect probability theory to algorithmic intuition.

What it tests

This problem class is governed by the structure of the coupon collector process, where each step involves randomly sampling from a finite set and tracking the accumulation of unique outcomes. The expected time to collect all unique items is the sum of expected waiting times for each new item, which increases as fewer uncollected items remain. The key is that the probability of obtaining a new item decreases as the collection grows, leading to a harmonic series structure in the expected value. This arises because, at each stage with $k$ collected items out of $n$, the probability of getting a new one is $(n-k)/n$, so the expected waiting time for the next new item is $n/(n-k)$. The pattern holds because the process is memoryless and each trial is independent, making the expected time additive over stages.