Reservoir Sampling from an Unknown-Length Stream

Reported in interviews at Bank of America Jane Street Meta Stackadapt Two Sigma Virtu Financial

Problem statement

You are processing a data stream of unknown length $n$, one element at a time, and you cannot store the entire stream.

Implement the function:

def reservoir_sample(stream, k, seed):
    ...

It performs Vitter's Algorithm R (reservoir sampling) to draw $k$ items without replacement from stream, pinned to a canonical RNG so the output is deterministic:

  1. Create rng = random.Random(seed).
  2. Fill the reservoir with the first k items.
  3. For each later item at 1-based position i, draw j = rng.randint(1, i); if j <= k, replace reservoir[j-1] with that item.
  4. Return the reservoir (a list of length min(k, len(stream)), in slot order).

Conceptually: each new element gets a fair shot at replacing a current selection, calibrated with decreasing probability $k/i$ so that after the whole stream, every size-$k$ subset is equally likely. The algorithm uses $O(k)$ memory, a single pass, and exactly $n-k$ random draws.

Example

reservoir_sample([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4, 2024) -> [9, 4, 7, 1]

The first 4 items fill the reservoir as [9, 8, 7, 6]; later items at positions 5..10 each draw j = rng.randint(1, i) and, when j <= 4, overwrite that slot; after processing the full stream two slots have been replaced, yielding [9, 4, 7, 1].

Show hint

If you already hold a fair sample of what came before, with what probability should a newly arriving item be let in?

Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.

Related free problems