Reservoir Sampling

# Reservoir Sampling ## Difficulty Medium ## Tags `algorithm`, `probability`, `randomization` ## Problem Statement Given a stream of elements of unknown length, randomly select `k` elements from the stream such that each element has an equal probability of being selected. You must process the stream in a single pass (cannot store all elements). ## Constraints - Stream length is unknown and potentially very large. - Use O(k) extra space only. - Each of the n elements should have probability k/n of being in the final sample. ## Signatures ### Python ```python def reservoir_sample(stream: Iterator[int], k: int) -> List[int]: pass ``` ### Java ```java public class Solution { public List<Integer> reservoir_sample(Object stream, int k) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<int> reservoir_sample(Object stream, int k) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<int> reservoir_sample(Object stream, int k) { } }; ``` ### C ```c int* reservoir_sample(Object stream, int k) { } ``` ### Ruby ```ruby def reservoir_sample(stream, k) end ``` ### Perl ```perl sub reservoir_sample { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def reservoir_sample(stream: Object, k: Int): List[Int] = { } } ``` ### Haskell ```haskell reservoir_sample :: ... -> ... reservoir_sample args = undefined ``` ### Clojure ```clojure (defn reservoir_sample [stream k] ) ``` ### Scheme ```scheme (define (reservoir_sample stream k) ) ``` ## Examples ### Example 1 **Input:** ``` stream = [1, 2, 3, 4, 5] k = 2 ``` **Output:** ``` [2, 4] # One possible output ``` **Explanation:** Each pair has probability 2/5 × 1/4 = 1/10 (there are C(5,2)=10 pairs). ### Example 2 **Input:** ``` stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 1 ``` **Output:** ``` [7] # Each number has 1/10 probability ``` ## Hints 1. The key insight: element i replaces an existing element with probability k/(i+1). 2. Each element in the final reservoir has probability k/n. 3. This can be proven by induction on the stream length.