Algorithms and Data Structures · Senior · Question 17 of 75
How do you pick a uniformly random sample of k items from a stream of unknown length?
- 1Keep every k-th item as the stream goes past
- ✓Correct answer: Reservoir sampling: keep item i with probability k/i
- 3Store the whole stream, then shuffle and take k
Explanation
After any number of items each one is in the reservoir with equal probability k/n, using O(k) memory and one pass. Taking every k-th item isn't uniform and depends on the stream length.