Reservoir Sampling: Uniform k-of-n Sample From a Stream of Unknown Length
Company: StackAdapt
Role: Machine Learning Engineer
Category: Statistics & Math
Difficulty: medium
Interview Round: Onsite
Overview: Design a one-pass algorithm that keeps a uniform random sample of k items from a stream whose length is unknown in advance, using memory proportional to k. Tests the replacement rule, an inductive proof that every item is kept with equal probability, complexity, and edge cases.