Skip to content

Latest commit

 

History

History
4 lines (4 loc) · 302 Bytes

File metadata and controls

4 lines (4 loc) · 302 Bytes

Reservoir Sampling

If there are unlimited data flow or incoming stream data of elements, we need to sample one elements from all elements, such that at any point during the processing of the flow, we return an element from the elements we have read so far.
time: O(1) - amortized
space: O(1)