Random element from the stream with uniform probability

February 6, 2024

Problem # Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability. Solution Approach # The task described is a classic problem in computer science, often solved using a technique known as Reservoir Sampling. The specific case of picking a single random element from a stream can be considered as Reservoir Sampling with a reservoir size of 1. Here’s how to approach the problem: ...