Reservoir Sampling and Fisher-Yates Shuffle: Randomized Algorithm Questions in Coding Interviews
3 views
Randomized algorithm questions show up less often than graphs or dynamic programming, but when they do, they catch many candidates off guard. The two that appear most often are reservoir sampling and the Fisher-Yates shuffle. Both are short to code, and both are really tests of whether you can reason about probability out loud.
Reservoir sampling: picking k items from a stream
The classic prompt: "You are given a stream of unknown length. Return one element chosen uniformly at random, using O(1) extra memory." You cannot store the stream, and you do not know n in advance.
The algorithm keeps a single candidate. When you see the i-th element (1-indexed), replace the candidate with it with probability 1/i. That's it.
import random
def sample_one(stream):
chosen = None
for i, x in enumerate(stream, start=1):
if random.randrange(i) == 0:
chosen = x
return chosen
The interviewer will almost always ask why this is uniform. The clean argument: element i is chosen at step i with probability 1/i, and survives each later step j with probability (j-1)/j. Multiply those together and the product telescopes to 1/n. Practice saying that sentence; it is the real answer they are scoring.
The generalization to k items keeps a reservoir of the first k elements, then for element i > k picks a random index r in [0, i). If r < k, replace reservoir[r]. Each element ends up in the final sample with probability k/n.
Common follow-ups:
- Weighted sampling (each item has a weight): use the key u^(1/w) with a min-heap of size k, known as the A-Res algorithm.
- Distributed streams: sample each shard, then merge by weighting each shard's sample by its count.
- LeetCode 382 (Linked List Random Node) and 398 (Random Pick Index) are direct applications.
Fisher-Yates shuffle
"Shuffle an array so that every permutation is equally likely." The correct version walks from the end, swapping each position with a random index at or before it:
def shuffle(a):
for i in range(len(a) - 1, 0, -1):
j = random.randint(0, i)
a[i], a[j] = a[j], a[i]
return a
The bug interviewers love to probe is the naive version that swaps each index with any random index in the whole array. It produces n^n equally likely execution paths, but there are n! permutations, and n^n is not divisible by n! for n > 2, so some permutations must be more likely than others. If you can explain that counting argument, you have shown exactly the kind of reasoning the question exists to test.
How to talk through these questions
1. State the constraint that makes the problem hard (unknown length, O(1) memory, uniformity).
2. Propose the algorithm before writing code.
3. Prove uniformity with a short probability argument, not "it seems random."
4. Mention testing: run it a million times on a small input and check the frequency of each outcome is close to expected.
The hardest part in a live interview is usually not the code but staying calm enough to produce the proof while someone watches. Rehearsing the explanation out loud helps, and tools such as Linkjob AI (https://linkjob.ai) can give real-time help during live technical interviews when you need a nudge on structuring an answer like this. Either way, if you can explain why 1/i works and why the naive shuffle is biased, you will be ahead of most candidates on this topic.