Reservoir Sampling
~20 mincode completion
Implement reservoir_sample(stream, k, seed) that returns a NumPy array of k elements.
Examples
k equals stream length: reservoir is the full stream
- Input
- reservoir_sample([1, 2, 3], 3, 0)
- shape of result
- [3]
Output size is always k
- Input
- reservoir_sample([10, 20, 30, 40, 50], 3, 0)
- shape of result
- [3]
k=1 always returns a single element
- Input
- reservoir_sample([5, 6, 7, 8], 1, 42)
- shape of result
- [1]
Hints
Hint 1
Loop a fixed number of times and update the running value each pass.
Hint 2
Reach for algorithm r rather than np random choice.
Requirements
stream: 1D array of valuesk: Sample size: Random seed for reproducibility
Return 1D NumPy array of k selected items.
Constraints
Allowed library: NumPy only
Time limit: 200 ms, Memory: 64 MB
Where this shows up
~20 min
••••••••••••••••
8 employers weight this skill
4 big tech firms, 1 AI product company, 1 enterprise vendor, 1 defense company, 1 quant fund. Top match scores 93.
Python
import numpy as np
def reservoir_sample(stream: np.ndarray, k: int, seed: int) -> np.ndarray:
"""
Select k items uniformly at random from stream using reservoir sampling.
Args:
stream: 1D array of values
k: Sample size
seed: Random seed for reproducibility
Returns:
1D NumPy array of k selected items.
"""
# YOUR CODE HERE
pass