How do you sample uniformly from an infinite stream?

Reservoir Sampling

Design an algorithm to select exactly k items randomly from an infinite stream of data where the total number of items n is unknown until the stream ends. Each item in the stream must have an equal probability k/n of being selected.

Requirements

• You do not know the total number of items beforehand.
• You cannot store all items from the stream in memory.
• The algorithm should process each element exactly once.

Function Signature

class ReservoirSampler:
    def __init__(self, k):
        # Initialize with sample size k
        pass

    def process_element(self, element):
        # Process a new element from the stream
        pass

    def get_sample(self):
        # Return the current k items
        pass

Examples

Example 1:

• k = 1. Stream: [10, 20, 30]
• Step 1: Process 10. Sample: [10] (prob 1/1)
• Step 2: Process 20. Sample: [20] (prob 1/2 to replace 10)
• Step 3: Process 30. Sample: [20] (prob 1/3 to replace 20, 2/3 to keep 20)

Constraints

• Memory usage should be O(k).
• Time complexity per element should be O(1).

Edge Cases

• What if the stream has fewer than k items?
• How to handle empty streams?