How do you sample uniformly from an infinite stream?

Q: How do you sample uniformly from an infinite stream?

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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)?

How do you sample uniformly from an infinite stream?

Quick Overview

Coding (Python) — Random sampling from an infinite stream

Task

Requirements

Follow-ups (if time)

Comments (0)