Implement stream random sampling in Python

Q: Implement stream random sampling in Python

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

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

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.

Implement stream random sampling in Python

Quick Overview

Comments (0)