How do you sample uniformly from an infinite stream?
Company: LinkedIn
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Coding (Python) — Random sampling from an infinite stream
You receive an **unbounded/infinite stream** of items (e.g., numbers or events). You cannot store all items.
### Task
Write Python code to maintain a **uniform random sample** of size `k` from all items seen so far.
### Requirements
- Each of the `n` items seen so far should have probability `k/n` of being in the sample.
- Use **O(k)** memory.
- Stream arrives one item at a time.
### Follow-ups (if time)
- Prove/argue why the algorithm is uniform.
- What changes if `k=1`?
- How would you handle weighted sampling (items have weights)?
Quick Answer: This question evaluates understanding of streaming algorithms, randomized sampling and probability, and algorithmic space–time trade-offs involved in maintaining a uniform sample from an unbounded data stream.