CODING CHALLENGE · N°47

Reservoir Sampling

Medium SamplingStreamingProbability

Pick k items uniformly at random from a stream of unknown length — in one pass, using O(k) memory, never storing the whole thing. It’s how you sample from a firehose of logs or an endless feed. Here the random draws are supplied, so the result is deterministic and testable. Solve it in Python or TypeScript, with hidden tests.

The problem

Implement reservoir(stream, k, randoms). Keep a "reservoir" of the first k items. For each later item at index i (i ≥ k), you are given a random integer randoms[i-k] uniformly in [0, i]; if it is less than k, replace reservoir slot randoms[i-k] with stream[i]. Return the final reservoir. (Supplying the randoms makes the normally-random algorithm deterministic so it can be tested — the logic is exactly real reservoir sampling.)

EXAMPLE 1

Input stream = [1,2,3,4,5], k = 2, randoms = [0, 5, 1]

Output [3, 5]

i=2 draws 0<2 → slot0=3; i=3 draws 5 (skip); i=4 draws 1<2 → slot1=5

CONSTRAINTS

The reservoir starts as the first k items of the stream.
For item i ≥ k, use randoms[i-k] (a draw in [0, i]): if it is < k, overwrite that reservoir slot; otherwise keep the reservoir unchanged.
One pass, O(k) memory — you never store more than k items regardless of stream length. The trick gives every item an equal 1/N chance of ending up in the reservoir.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement reservoir(stream, k, randoms): fill the reservoir with the first k items, then for each subsequent index i use the provided draw to decide whether (and where) to replace. Return the reservoir.

HINTS — 4 IDEAS

Copy the first k items into the reservoir. If the stream has ≤ k items, that is the answer.
For each index i from k onward, read j = randoms[i-k] (the draw in [0, i]).
If j < k, the new item wins slot j: reservoir[j] = stream[i]. Otherwise it is discarded.
That j < k probability is exactly k/(i+1), which is what keeps every item equally likely to survive.

CPython · WebAssembly

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Real-time & Messaging Algorithms & DSA