Reservoir Sampling

Medium · Math & Number Theory · about 20 minutes

Asked at Google, Meta, Netflix, Databricks, Cohere, Hugging Face.

Pick k items uniformly at random from a stream whose length you don't know in advance, using O(k) memory.

To make the result checkable, the random numbers are supplied: for the element at stream index i (0-indexed, i >= k), the random integer drawn uniformly from [0, i] is rand[i - k]. Implement Algorithm R with these draws and return the final reservoir.