Algorithm1 Practice1 Interview

Reservoir Sampling

GuideCode Labs

Maintain an unbiased sample from a stream whose total length is unknown in advance. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Reservoir Sampling when the prompt's constraints and required operations match this shape: Maintain an unbiased sample from a stream whose total length is unknown in advance.

On this page · Keep a Uniform Sample from a Stream

Checking your account…

Keep a Uniform Sample from a Stream

Reservoir sampling selects from a stream of unknown length without storing all items. After processing i items, the reservoir invariant gives each seen item equal inclusion probability.

Replace with Decreasing Probability

For a one-item reservoir, keep the first item, then replace it with item i using probability one over i when counting items from one. An integer draw over all seen positions implements that probability exactly.

Trace Reservoir Decisions

Reference

def reservoir_trace(values,draws):
    if not values:return []
    sample=values[0];trace=[]
    for index,item in enumerate(values[1:],1):
        draw=draws[index-1];replaced=draw==0
        if replaced:sample=item
        trace.append([item,draw,replaced,sample])
    return trace

Practice

Implement reservoir_trace(values,draws). For item index i after the first, draws supplies an integer in [0,i]; return [item,draw,replaced,sample].

def reservoir_trace(values,draws):
    pass

Public tests

Replace on one of i plus one outcomes

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Generalize from One Item to K

Fill k reservoir slots, then for seen count i draw uniformly from zero through i minus one. Replace a slot only when the draw is below k, preserving inclusion probability k over i.

Sample One with Deterministic Draws

Reference

def sample_one(values,draws):
    if not values:return None
    sample=values[0]
    for index,item in enumerate(values[1:],1):
        if draws[index-1]==0:sample=item
    return sample

Practice

Implement sample_one(values,draws). Return one reservoir sample using supplied draws for testability, or None for empty input.

def sample_one(values,draws):
    pass

Public tests

Expose random decisions as input

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Require an Explicit Random Source

Production code may accept an RNG object; tests should inject deterministic draws. Modulo-reducing arbitrary random integers can introduce bias unless the source range divides evenly.

Explain It in an Interview

Say: “After i items, each has probability one over i of occupying the sample. The new item replaces with that probability, while every prior item survives with the complementary probability.” State one-pass time, O(k) space, and empty behavior.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Reservoir Sampling proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Reservoir Sampling complete workflow	`O(n)`	`O(n)`	Seed k items, then map each supplied uniform stream-index draw to either one replacement or no change.

Space

O(k) for the focused Simulate Reservoir Sampling implementation.

Assumptions

The documented draw rule is applied exactly once per remaining item and the reservoir size stays k. This deterministic interface is the testable state transition used by reservoir sampling.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Reservoir Sampling invariant before coding and preserve it after every update, traversal step, or recursive return.
The processed prefix or sample has the target distribution for all items seen so far.
The random index range includes every and only currently eligible choice.
Seed the reservoir with the first k items. Preserve this claim after every transition.
Apply each deterministic replacement draw at the matching stream index. Preserve this claim after every transition.

When To Use Or Avoid Reservoir Sampling

Use It When

Use Reservoir Sampling when this precondition is stated or can be proved: Each random choice is uniform over the documented candidate range and uses an unbiased random source.
Use it when this maintained state removes repeated work: The processed prefix or sample has the target distribution for all items seen so far.

Choose Another Tool When

Avoid Reservoir Sampling when this precondition is absent: Each random choice is uniform over the documented candidate range and uses an unbiased random source.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Each random choice is uniform over the documented candidate range and uses an unbiased random source.

Avoid

def reservoir_sample(values, k, draws):
    pass

Use instead

def reservoir_sample(values, k, draws):
    reservoir = list(values[:k])
    for stream_index, value in enumerate(values[k:], start=k):
        draw = draws[stream_index - k]
        if draw < k:
            reservoir[draw] = value
    return reservoir

Where you will hit this: Simulate Reservoir Sampling(opens in a new tab)

Breaking the state transition

Appends selected values and lets the reservoir grow.

Prevent it: Preserve this proof obligation: Induction shows each eligible item or permutation retains the required equal probability after every update.

Avoid

def reservoir_sample(values,k,draws):
    out=list(values[:k])
    for value,draw in zip(values[k:],draws):
        if draw<k:out.append(value)
    return out

Use instead

def reservoir_sample(values, k, draws):
    reservoir = list(values[:k])
    for stream_index, value in enumerate(values[k:], start=k):
        draw = draws[stream_index - k]
        if draw < k:
            reservoir[draw] = value
    return reservoir

Where you will hit this: Simulate Reservoir Sampling(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

def reservoir_sample(values,k,draws):
    out=list(values[:k])
    for value,draw in zip(values[k:],draws):
        if draw<k:out.append(value)
    return out

Use instead

def reservoir_sample(values, k, draws):
    reservoir = list(values[:k])
    for stream_index, value in enumerate(values[k:], start=k):
        draw = draws[stream_index - k]
        if draw < k:
            reservoir[draw] = value
    return reservoir

Where you will hit this: Shortest Subarray With OR at Least K(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…