Coding interview: How do you sample uniformly from an unknown-length stream?

Prompt and use cases

You can read the stream only once; its length n is unknown, and you need k distinct items with equal probability. You cannot store the stream or wait for a final random index. Reservoir sampling keeps a fixed reservoir of size k: when item i arrives, it enters with probability k/i and replaces a uniformly chosen reservoir slot.

This prompt tests a randomized streaming algorithm. Vitter’s paper studies one-pass sampling when the population size is unknown, and university course notes give the uniformity induction. The core category is coding: probability invariants under a memory bound, not a data-platform implementation.

What the interviewer evaluates

• Whether you recognize the unknown-size, one-pass, fixed-memory reservoir pattern.
• Whether you explain the k=1 1/i replacement rule before generalizing to k.
• Whether you prove that after item i, every item has probability k/i in the sample.
• Whether you avoid duplicate samples, a false known-n assumption, and biased random integers.
• Whether you state O(n) time, O(k) space, and the boundary of weighted sampling.

Clarifications before answering

• Is k a positive integer? What should happen for k <= 0 or fewer than k stream items?
• Does “distinct” mean distinct records or deduplication by value?
• Can the stream be empty, infinite, or interrupted? Output and recovery differ.
• Is the final reservoir the only output, or must it be observable during the scan?
• Does the random API provide unbiased integers over the required range?
• Is the target uniform or weighted/stratified? Weighted sampling needs a different invariant.

30-second answer framework

“Fill the reservoir with the first k items. For item i, starting at one, generate an unbiased integer j in [0, i-1]. If j < k, replace reservoir[j]; otherwise discard the item. After item i, every item has probability k/i: the new item enters with k/i, and an old item survives with k/(i-1) times 1 - 1/i. The algorithm is one pass, O(n) time, and O(k) extra space.”

Step-by-step deep answer

Step 1: Start with k=1.

Keep the first item. For item i, replace the current candidate with probability 1/i. After processing i items, each has probability 1/i of being retained.

Step 2: Generalize to k.

Fill the first k slots. For item i, enter with probability k/i; if it enters, choose one of the k slots uniformly. An integer j in [0, i-1] implements this: j < k means replace slot j.

Step 3: Write the pseudocode.

reservoir = first k items
for i = k+1 .. n:
  j = uniformInteger(0, i-1)
  if j < k:
    reservoir[j] = item i
return reservoir

If the stream cannot be prefilled, append while seen <= k, then use the same branch. The integer generator must cover the complete range without bias.

Step 4: Prove the new item’s probability.

At item i, its inclusion probability is k/i. Once included, it survives every later step with probability ∏(1 - 1/t) = i/n, because a particular slot is replaced with probability 1/t. Its final probability is therefore k/i × i/n = k/n.

Step 5: Prove the old item’s probability.

Assume each old item has probability k/(i-1) after item i-1. At step i, it is replaced with probability k/i × 1/k = 1/i, so it survives with 1 - 1/i. Its new probability is k/(i-1) × (i-1)/i = k/i. The new and old items satisfy the same invariant.

Step 6: Analyze complexity and random generation.

Each item is processed once: O(n) time. The reservoir holds k items: O(k) extra space. For counts beyond safe integer precision, use an unbiased integer API that supports the required range.

Step 7: Handle input boundaries.

An empty stream returns an empty sample. k = 0 returns an empty sample or raises the documented error. If fewer than k items arrive, return the actual items or fail according to the contract. Deduplication by value requires extra state and may violate O(k).

Step 8: Explain weighted and distributed extensions.

Weighted sampling changes the target distribution, so equal-probability replacement is invalid; discuss weighted-reservoir keys such as Efraimidis–Spirakis. Distributed reservoirs need counts and priorities/weights to merge correctly; concatenating shard samples is biased.

High-quality sample answer

“I maintain a reservoir of capacity k. Fill it with the first k items. For item i = k+1 onward, draw an unbiased integer j in [0, i-1]; if j < k, replace slot j, otherwise discard. The new item enters with probability k/i. A specific old item is replaced with probability 1/i, so its probability changes from k/(i-1) to k/(i-1) × (1-1/i) = k/i. By induction every item has final probability k/n. The algorithm is one pass, O(n) time, and O(k) space. I test empty input, k=1, k=0, repeated records, repeated simulations, and explicitly re-derive the invariant for weighted or distributed variants.”

Common mistakes

• Store the entire stream first → violates unknown-size and memory constraints → update the reservoir online.
• Use 1/k for every new item → probabilities do not adapt to i → use k/i.
• Use random() % i → modulo can be biased → use unbiased integer sampling.
• Choose replacement slots non-uniformly → some combinations become more likely → select among k slots uniformly.
• Use k/n while scanning → n is unknown and the probability changes each step → use the current count i.
• Ignore duplicate semantics → distinct records and distinct values differ → clarify deduplication first.
• Concatenate shard reservoirs → unequal shard sizes bias the result → merge with counts and priorities.
• Reuse the uniform algorithm for weights → the target distribution changed → use weighted reservoir sampling with a new proof.

Follow-up questions and responses

Follow-up 1: Why is the new item’s replacement probability k/i?

At item i, the algorithm chooses one of i positions uniformly. The first k positions represent the reservoir, so the chance of hitting one is k/i.

Follow-up 2: How do you prove fairness for k=1?

The first item is kept with probability one. Item i replaces it with 1/i; any old item survives with (1/(i-1)) × (1-1/i) = 1/i, giving the induction.

Follow-up 3: How do you generate an unbiased integer?

Use a uniform-integer API, or rejection sampling that discards random values outside the largest divisible range. Do not assume simple modulo is always unbiased.

Follow-up 4: What if the stream ends before k items?

Return the actual items or raise the documented error. Never fabricate entries; state the behavior before coding.

Follow-up 5: How would you sample with weights?

Define the weighted target distribution, then use weighted-reservoir random keys or exponential/log transforms. The uniform k/i proof no longer applies directly.

Follow-up 6: How would you merge distributed reservoirs?

Each shard carries its item count and enough random priority or weight information. Merge according to the global sampling rule; direct concatenation or random truncation favors smaller shards.

Follow-up 7: How do you validate uniformity?

Run many trials on a fixed short stream, compare each item’s inclusion frequency with k/n, and test boundaries and reproducible seeds. Statistics can reveal bias, but they do not replace the probability proof.