Simulate Reservoir Sampling

Practice Exercise Intermediate Medium Array Reservoir Sampling

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement reservoir_sample(values, k, draws). Start with the first k values. For stream index i >= k, draws[i-k] is in [0,i]; replace reservoir[draw] when draw < k. Return the final reservoir.

Starter code

def reservoir_sample(values, k, draws):
    pass

Test cases

replace-and-skip

Expected: [50,30]

keep-seed

{
  "args": [
    [
      1,
      2,
      3,
      4
    ],
    2,
    [
      2,
      3
    ]
  ]
}

Expected: [1,2]

Wizard outline

Step 1: Seed the fixed-size reservoir
Copy the first k stream values into independent storage. Before later items compete for slots, every initial item is selected.
Step 2: Process one later stream item
Use the first deterministic draw to decide one replacement. A draw below k selects the reservoir slot replaced by the new item.
Step 3: Process every remaining stream item
Pair each later value with its deterministic draw. The same bounded replacement rule applies independently at every stream index.

Footguns and prerequisites

Using the reservoir index instead of the stream index changes probabilities.
Appending after the seed grows the reservoir beyond k.
functions
lists and tuples
control flow

Reviewed references

Python More on Lists

Recommended approach and implementation

Seed k items, then map each supplied uniform stream-index draw to either one replacement or no change.

Why it works: 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.

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