What is Reservoir Sampling?
Learn how reservoir sampling picks a uniform random sample from an unbounded stream in O(k) memory, with a full interview answer.
Expected Interview Answer
Reservoir sampling is a randomized algorithm that selects a uniformly random sample of k items from a stream of unknown or unbounded length, using only O(k) memory and a single pass over the data.
The algorithm fills a 'reservoir' array with the first k items directly, then for every subsequent item at index i (0-indexed, i >= k) it generates a random integer j between 0 and i inclusive; if j is less than k, the item replaces the reservoir's j-th slot, otherwise it is discarded. This decreasing-probability replacement rule guarantees every item seen so far has exactly a k/n chance of being in the final reservoir once n items have streamed through, regardless of how large n grows or whether n is known in advance. It is essential when data arrives as an unbounded stream — server logs, live sensor feeds, or paginated APIs — where storing the whole dataset to sample from is impossible. The classic k=1 case reduces to picking one item uniformly at random from a stream with no prior knowledge of its length.
- O(k) memory regardless of stream length
- Single pass, no need to know total count upfront
- Provably uniform sampling probability for every item
- Works on live, unbounded, or paginated data streams
AI Mentor Explanation
Reservoir sampling is like a scout who must pick exactly 3 standout players from an unknown-length stream of trial candidates walking through the nets, without knowing how many will show up all day. The scout keeps the first 3 candidates automatically, then for every new candidate rolls a random number up to the count seen so far; if that number lands inside the reservoir's range, the new candidate swaps in for a randomly chosen one of the current 3. By closing time, no matter whether 50 or 5,000 candidates walked through, each one had an exactly equal chance of being among the final 3 picks. This is why the scout never needs to know the day's total headcount in advance to guarantee fairness.
Step-by-Step Explanation
Step 1
Fill the reservoir
Copy the first k items from the stream directly into a reservoir array of size k.
Step 2
Process each subsequent item
For item at 0-indexed position i (i >= k), generate a random integer j in [0, i].
Step 3
Conditionally replace
If j < k, overwrite reservoir[j] with the current item; otherwise discard the item.
Step 4
Repeat until the stream ends
The final reservoir holds k items, each with exactly k/n probability of inclusion once n total items have streamed by.
What Interviewer Expects
- Explain why the algorithm works without knowing the stream length in advance
- State O(k) space and O(n) time for a single pass over n items
- Walk through the probability argument for why each item has k/n chance of inclusion
- Name real use cases: sampling live logs, unbounded streams, paginated APIs
Common Mistakes
- Assuming the stream length must be known beforehand
- Forgetting to seed the random replacement with the running index i, not a fixed range
- Confusing reservoir sampling with simple random shuffling of a known-size array
- Not recognizing k=1 as the simplest special case
Best Answer (HR Friendly)
“Reservoir sampling lets me pick a fair random sample from a stream of data even when I have no idea how much data is coming, using only a small fixed amount of memory. I keep the first few items, then for every new item that arrives I give it a shrinking chance of swapping into my sample, which mathematically guarantees every item ends up equally likely to be chosen.”
Code Example
import random
def reservoir_sample(stream, k):
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoir
# Works even if 'stream' is an unbounded generator
def line_stream(path):
with open(path) as f:
for line in f:
yield line.rstrip("\n")
sample = reservoir_sample(line_stream("huge_log.txt"), k=5)Follow-up Questions
- How would you prove each item ends up with probability k/n of being selected?
- How would you adapt reservoir sampling for weighted sampling?
- How would you parallelize reservoir sampling across multiple worker shards?
- What happens to the algorithm if k=1?
MCQ Practice
1. What is reservoir sampling's space complexity for sampling k items from a stream of n items?
Only the reservoir of size k is kept in memory at any time, independent of the total stream length n.
2. Why is reservoir sampling useful for streaming data?
The algorithm processes items one at a time and never needs to know n in advance, making it ideal for unbounded streams.
3. When processing the item at 0-indexed position i (i >= k), what determines if it replaces a reservoir slot?
The decreasing-probability replacement rule (j < k out of i+1 possibilities) is what guarantees uniform final probability.
Flash Cards
What problem does reservoir sampling solve? — Uniformly sampling k items from a stream of unknown or unbounded length.
What is the space complexity of reservoir sampling? — O(k), independent of the total stream length.
How is a new item at position i (i >= k) handled? — A random j in [0, i] is drawn; if j < k, the item replaces reservoir[j].
What is the probability any single item ends up in the final reservoir? — Exactly k/n, once n total items have streamed through.