Implement stream random sampling in Python
Company: LinkedIn
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an unbounded stream of items that cannot be stored entirely in memory. Write Python code to maintain a uniform random sample from the stream.
The standard form of this problem is reservoir sampling: after seeing `n` items, every item seen so far should have equal probability of being included in a reservoir of size `k`. Your solution should work even when the total stream length is unknown in advance.
Explain the algorithm, and discuss its time complexity, space complexity, and any edge cases.
Overview: This question evaluates understanding of streaming algorithms, uniform random sampling, and probabilistic guarantees for maintaining a fixed-size sample from an unbounded data stream (reservoir-sampling concepts).