34. Reservoir Sampling for an Eval Set

Problem

A lab wants to build a fixed-size eval set by sampling uniformly from a much larger stream of candidate examples (e.g. production transcripts flowing through a logging pipeline) whose total length isn't known in advance and is too large to hold in memory all at once.

Maintain a uniformly-random sample of size k using only O(k) memory as the stream flows past, one item at a time — the classic Reservoir Sampling problem (Algorithm R). The stream must be processed as a single forward pass, never looking back or peeking at its total length in advance.

Source: src/34_reservoir_sample_eval_set.py

def reservoir_sample_eval_set(stream: list[str], k: int, seed: int) -> list[str]:
    ...

Examples:
>>> reservoir_sample_eval_set(["ex_a", "ex_b", "ex_c"], k=5, seed=0)
# k >= len(stream), so the reservoir equals the stream exactly, in order.
['ex_a', 'ex_b', 'ex_c']

>>> reservoir_sample_eval_set([f"ex_{i}" for i in range(10)], k=3, seed=42)
# len(stream) > k: reservoir holds 3 items, each stream element had an
# equal 3/10 chance of surviving to the end -- exact contents are the
# seed's deterministic output.
['ex_4', 'ex_1', 'ex_9']

Step-by-Step Approach

1. For the first k items in the stream (indices 0 through k-1), unconditionally fill the reservoir with them — there's nothing to compare against yet.
2. For every subsequent item at index i (i >= k), it must be included in the final sample with probability k/(i+1) to keep the overall distribution uniform. Generate a random integer j uniformly in [0, i].
3. If j < k, the item survives: overwrite reservoir[j] with the new item (evicting whatever was there). Otherwise the item is discarded and the reservoir is untouched.
4. Prove to yourself why this maintains uniformity: at the moment item i is processed, each of the k reservoir slots holds some earlier item with equal probability, and the new item claims any specific slot with probability 1/(i+1) times k possible slots = k/(i+1) — matching the required inclusion probability without ever needing to know the stream's total length.
5. Seed all randomness through a single random.Random(seed) instance (rather than the global random module) so results are exactly reproducible given the same seed.
6. Handle edge cases: k=0 returns an empty reservoir immediately (every item is discarded, since j can never be < 0), and k >= len(stream) means every item lands in the fill phase, so the reservoir ends up holding the entire stream in original order.

The key insight is that Algorithm R never needs to know the stream's total length in advance and never revisits an earlier item — each new item is independently accepted or rejected with exactly the probability needed to keep the running sample uniform, which is what makes true streaming (unbounded, one-pass, O(k) memory) sampling possible at all.

Reference solution

import random


def reservoir_sample_eval_set(stream: list[str], k: int, seed: int) -> list[str]:
    # Algorithm R: O(n) time (one pass), O(k) space (the reservoir itself)
    rng = random.Random(seed)
    reservoir: list[str] = []
    for i, item in enumerate(stream):
        if i < k:
            # fill phase: first k items are always kept
            reservoir.append(item)
        else:
            # item i (0-indexed) survives with probability k/(i+1)
            j = rng.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir

Key Functions & Tricks

• random.Random(seed) — an isolated, seeded RNG instance, not the shared global random module state, so results are exactly reproducible
• rng.randint(0, i) — the core probability trick: a uniform draw over an ever-growing range, whose acceptance-into-reservoir probability naturally decays as i grows
• Fill phase then replace phase — the first k items need no randomness at all; only items beyond index k-1 compete for a slot
• enumerate(stream) — processes the stream as a single forward pass without ever calling len(stream)
• Algorithm R — the textbook name for this exact technique, worth naming explicitly in an interview

How to Recognize This Pattern