Prove reservoir sampling correctness
Overview
This question evaluates randomized and streaming algorithm skills, including mastery of reservoir sampling, induction-based correctness proofs, probability reasoning, and complexity analysis for sampling under strict memory constraints.
Other
Oct 13, 2025, 9:49 PM
Data Scientist
Onsite
Coding & Algorithms
0
0
Design an algorithm to sample k items uniformly at random from a stream of unknown and potentially massive length N, using O(k) memory and one pass. (a) Write the algorithm for k=1 and generalize to k>1. (b) Prove by induction that after processing i items, each seen item has probability k/i to be in the reservoir. (c) Discuss time and memory complexity, and outline how you would adapt it for weighted sampling.