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

Approach, complexity & discussion — open after you solve

The approach

To pick k items uniformly from a stream of unknown length in one pass: keep the first k in a reservoir, then for the i-th item (with i > k) replace a random reservoir slot with probability k/i. A short induction shows every item that has arrived is equally likely to be in the reservoir — no need to know the total up front.

Complexity

Time O(n), space O(k) — a single pass with fixed memory regardless of stream length.

Common mistakes

Requiring the total count first — that defeats the entire point of the algorithm.
Using the wrong replacement probability (it must be exactly k/i).
Biasing toward early or late items by mishandling the boundary at i = k.

Where this shows up

Reservoir sampling draws a uniform random sample from a stream you cannot hold in memory or whose size you do not know — log sampling, A/B bucketing, picking a random line from a huge file, or sampling high-volume telemetry. It is the canonical “fair sample in one pass” technique.

Finished this one? 0 / 75 Challenges done

Explore the topic

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

Real-time & Messaging Algorithms & DSA