Problem bank

Problem 75 of 333HardCodingP075

Reservoir sampling

  1. You receive a stream of elements one at a time, and you don't know its length in advance. Using constant memory, select one element so that every element is equally likely to be chosen.