Reservoir Sampling Interview Questions: Unknown Stream Length and Uniformity Proofs

Reservoir sampling interview questions ask for a uniform sample from a stream whose final length is unknown or too large to store. For one item, keep the first. When the i-th item arrives using one-based i, replace the reservoir with probability 1/i. After every prefix, each position seen so far is stored with probability 1/i.

Jeffrey Vitter's research is a primary technical source for reservoir algorithms and their analysis. The basic interview version is often called Algorithm R for a reservoir of size k. The proof matters more than memorizing random() < 1/i: correct integer bounds, insufficient-stream behavior, weights, and distributed merging all change the contract.

Reservoir Sampling Interview: Quick Answer

For one sample, enumerate items from i=1, draw j uniformly from 0..i-1, and replace when j==0. For k samples, fill the first k positions. At item i for i>k, draw j uniformly from 0..i-1; if j<k, replace slot j. The new item is included with probability k/i, and conditional on inclusion every slot is equally likely.

Prove the invariant. An older item was included after i-1 steps with probability k/(i-1) and survives step i with probability 1-1/i=(i-1)/i, so it remains with probability k/i. The new item enters with probability k/i. Return all items if the stream ends before k, or reject, according to the API.

Derive the One-Sample Rule

Assume after i-1 items each prior position is selected with probability 1/(i-1). At item i, choose the new item with probability 1/i; otherwise keep the old sample. A previous position's final probability is 1/(i-1) * (i-1)/i = 1/i. The new position also has probability 1/i. The invariant holds by induction from i=1.

Notice that the algorithm samples positions, not distinct values. If the stream is A,A,B, value A has two positions and should be returned with probability 2/3 under position-uniform sampling. Deduplicating first changes the population and requires storing identities or another algorithm.

Implement k Slots with Safe Random Bounds

from random import Random

def reservoir(stream, k, rng=None):
    if k < 0:
        raise ValueError("negative sample size")
    rng = rng or Random()
    result = []
    for i, item in enumerate(stream, 1):
        if i <= k:
            result.append(item)
        else:
            j = rng.randrange(i)  # exactly 0..i-1
            if j < k:
                result[j] = item
    return result

randrange(i) makes the interval explicit. Avoid int(random()*i) when the language's floating generator cannot represent all large integers uniformly. Avoid inclusive randint(0,i), which creates i+1 outcomes and the wrong probability. A seeded RNG makes tests reproducible; cryptographic sampling requires a suitable secure generator and a different threat model.

Prove k-Sample Uniformity

After i items, every position should have inclusion probability k/i, and every k-subset should be equally likely for the strongest uniform-without-replacement claim. At step i, the new item enters when j<k, probability k/i. A particular older item is currently included with probability k/(i-1). Conditional on being included, it is replaced only if j selects its one slot, probability 1/i, so survival is (i-1)/i.

Multiplying gives k/i. For subset uniformity, consider a final subset either containing the new item or not and count the unique preceding reservoir/replacement transitions; the same rule yields equal probability. In most interviews the marginal induction is accepted, but mention that distinct slots and uniform replacement preserve sampling without replacement.

Clarify Streams, Iterators, and Unknown Length

The algorithm reads each item once and stores O(k) items, so it works for generators, files, or live streams. Time is O(n) for Algorithm R, with one random draw per item after the reservoir fills. Vitter describes skip-based methods that can reduce random-number work for large streams, but lead with the simple correct version unless constraints demand them.

An infinite stream never produces a final uniform sample over all positions; it only maintains a uniform reservoir over the finite prefix observed at query time. If a process restarts, persist the reservoir, number of items seen, RNG state or an equivalent reproducible transition state. Resetting i to zero biases future samples toward post-restart items.

Do Not Reuse the Proof for Weighted Sampling

If items have unequal positive weights and inclusion should be proportional to weight, the k/i rule is wrong because i counts positions, not weight. Weighted reservoir methods assign random priority keys derived from weights and keep top priorities, with details depending on whether the goal is one draw, k draws without replacement, or repeatable distributed selection.

State the meaning of weight and behavior for zero or negative values. Heavy hitters are another different problem: estimating frequent values from a stream is not uniform sampling. Stratified sampling also needs a reservoir and seen count per stratum, plus an allocation policy. Do not relabel these tasks as minor parameter changes.

Merge Distributed Samples with Correct Weights

If partitions have different item counts, choosing one partition reservoir uniformly biases small partitions. For a one-item sample, choose partition p with probability n_p / sum n, then take its uniform local item. For a global k-sample, merge with a correct weighted method based on partition counts or assign composable random priorities to individual items.

Each worker must report the exact count represented and its sampling scheme. Missing a partition or using a stale count changes the target population. For deterministic replay, derive random priorities from a stable item/position ID and seed, but consider privacy and adversarial predictability. Distributed convenience does not excuse an unproved merge rule.

Test Randomness without Flaky Assertions

Unit tests should control the RNG to force no replacement, each replacement slot, k=0, k greater than stream length, and generator input. These tests verify branches and boundaries deterministically. A test that demands one exact result from an unseeded generator is flaky and says little about uniformity.

Statistical tests run many seeded trials on a tiny stream and compare inclusion counts with the expected probability using a tolerance chosen before results. They can catch an off-by-one such as drawing from 0..i, but a passing simulation is not a proof and can miss small bias. Keep the induction in the explanation.

Property checks assert output length min(k,n), every sampled object came from the stream, and no position appears twice for without-replacement sampling. Duplicate values need tagged positions during tests. Measure algorithm time and random calls separately if discussing skip optimizations.

Make the Answer Reviewable

Turn the reservoir sampling design into a small deterministic review before adding more scale. Write the initial state, five to ten timestamped inputs, every expected state transition, and the exact read result at two watermarks. Replay one input, deliver another out of order, pause one consumer, and rebuild the serving view from its durable boundary. The replay should not create an extra effect, the stale input should follow the declared version rule, and the rebuilt read should match the authoritative result through the same watermark.

Keep expected results independent of the implementation. If the same code produces both the output and the assertion, a shared assumption can hide the defect. Add one invariant check that scans all state, even if production serves a faster index. For a distributed design, say which part this fixture does not prove: it does not measure production latency, network partitions, or capacity. Load and fault tests come next, using the traffic and error budgets already stated.

Finish with an operational table: signal, healthy range, action, and user-visible consequence. Include ingestion or queue age, rejected or duplicate work, authoritative-versus-serving divergence, and tail read latency. This makes the proposal inspectable. An interviewer can now change one requirement and see exactly which state, test, and alert must change with it.

Separate what the review establishes from what it leaves open. A passing deterministic fixture proves the declared state transitions for those inputs. It does not establish performance at scale, fairness across real users, or behavior during every network failure. Add a capacity test for the estimated peak, a skew test concentrated on one key or partition, and a fault test at the acknowledgment boundary. Record versions and random seeds so failures can be replayed. When a result differs from expectation, reduce it to the smallest trace, name the violated invariant, and repair that transition before retuning capacity. This evidence-first sequence keeps correctness questions from being hidden inside infrastructure changes.

Keep the review artifact beside the implementation and date the environment that produced it. If a later optimization changes ordering, batching, numeric width, or retry behavior, rerun the same trace before accepting the new result. The invariant is the stable comparison point; the component diagram is not.

A 45-Minute Interview Structure

Spend four minutes on k, replacement, weights, output timing, and stream guarantees. Derive one-sample probability in five. Code k-sampling in ten and trace i=k+1. Use ten minutes for induction, seven for RNG and edge cases, and six for weighted or distributed follow-ups. Close with deterministic and statistical tests. Keep one-based i visible to prevent off-by-one probability mistakes.

Final Takeaway

Reservoir sampling maintains a uniform sample after every finite prefix without knowing final length. For k slots, include item i with probability k/i and replace a uniformly chosen slot. The induction proves both new and old positions have inclusion probability k/i. Declare random bounds, insufficient-stream behavior, and restart state, and do not reuse the proof for weighted or incorrectly merged distributed samples.

Sources and Further Reading

• Vitter: Random Sampling with a Reservoir
• Vitter paper DOI
• Python random.randrange
• Python secrets module

Documentation supports the stated system or algorithm behavior; individual question records support only their own practice contracts. Architecture recommendations and interview sequencing are editorial inference.