Coding & Algorithms · Interview Question
Draw a uniformly random element from a stream of unknown length in O(1) memory. How does reservoir sampling work?
How to answer
Keep one candidate; for the i-th element replace it with probability 1/i. After n elements each has probability 1/n. Element i survives with prob (1/i)·(i/(i+1))·…·((n-1)/n); the trailing factors telescope to i/n, leaving 1/n. O(1) space, single pass.
Key idea: Replacing with a fixed probability instead of 1/i (breaks uniformity), or being unable to show the telescoping product equals 1/n.
More: Quant interview prep · Quant salary
Related Coding & Algorithms questions
- A fair six-sided die pays you its face value in dollars. What is the risk-neutral fair price to play this game once, and why?
- Expected and worst-case time complexity of quicksort, and why does the expected case dominate in practice?
- Find for each array element whether its complement (target - x) exists. Naive is O(n²). Get it to O(n)?
- Given a sorted array, how do you find a target in O(log n), and what are the two most common bugs?