Reservoir Sampling
Reservoir Sampling
Reservoir sampling (Algorithm R) selects k items uniformly at random from a stream of unknown length n, using only O(k) memory regardless of how large the stream is.
Algorithm R:
1. Fill the reservoir with the first k items
2. For each subsequent item at position i (0-indexed, starting at k):
- Generate a random integer j in [0, i]
- If j < k, replace reservoir[j] with item i
For deterministic tests, use a seeded random number generator: rng = np.random.default_rng(seed).
Example: stream [10, 20, 30, 40, 50], k = 3, seed = 0
[10, 20, 30]Your task:
Implement reservoir_sample(stream, k, seed) that returns a NumPy array of k elements.
Example Tests
k equals stream length: reservoir is the full stream
Input: {"k":3,"seed":0,"stream":[1,2,3]}
Expected: [3]
Output size is always k
Input: {"k":3,"seed":0,"stream":[10,20,30,40,50]}
Expected: [3]
k=1 always returns a single element
Input: {"k":1,"seed":42,"stream":[5,6,7,8]}
Expected: [1]