Reservoir Sampling
Pick $k$ random items uniformly from a stream of unknown length using $O(k)$ memory.
Intermediate
Keep item with probability , replacing a random reservoir slot.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.