Implement Reservoir Sampling; Analyze Time and Space Complexity
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### 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.
Quick Answer: 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.
Given a list of integers nums, return a list of indices i such that nums[i] is a value that occurs more than once in nums. Return indices in increasing order. Implement an O(n) solution using only set() and enumerate() (no dictionaries, counters, or sorting).
Constraints
- 0 <= len(nums) <= 200000
- nums[i] fits in 32-bit signed integer
- Time complexity must be O(n)
- Use only set() and enumerate(); do not use dict, Counter, or sorting
- Return indices in increasing order
Hints
- First pass: use a set to track seen values and collect which values are duplicates.
- Second pass: use enumerate to collect indices whose values are in the duplicates set.
- No need to sort; enumerating maintains increasing index order.