Katkat
Back

Implement Reservoir Sampling; Analyze Time and Space Complexity

AmazonData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of streaming randomized algorithms and probabilistic reasoning—specifically reservoir sampling—along with analysis of time and space complexity and use of hash-based structures for duplicate detection; it is in the Coding & Algorithms domain and tests both conceptual probability invariants and practical implementation skills. Such problems are commonly asked to gauge a candidate's ability to design one-pass, linear-time solutions for unbounded data streams and to reason about algorithmic correctness and resource bounds in technical interviews.

Scenario

Process an unbounded stream of user IDs and maintain a uniform random sample of k users in memory.

Question

Implement reservoir sampling for an incoming stream; analyze its time and space complexity. Explain why the algorithm guarantees each element is selected with probability k⁄n. Given an array of integers, return indices of duplicate values using only set() and enumerate(). Provide O(n) code.

Hints

Focus on one-pass algorithms and probability invariants.