Coding questions · Amazon
Implement Reservoir Sampling; Analyze Time and Space Complexity
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.
Indices of Duplicate Values via Sets
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
Examples
Example 1
Input: nums = [1, 2, 3, 1, 2, 1]
Output: [0, 1, 3, 4, 5]
Explanation: Duplicate values are 1 and 2. Their indices in order are 0,1,3,4,5.
Example 2
Input: nums = [4, 5, 6, 7]
Output: []
Explanation: All values are unique; no indices to return.
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.
Approach
Traverse nums once to identify which values occur more than once using two sets: 'seen' for values observed and 'dup_vals' for values seen again. Then, traverse nums with enumerate and collect indices whose values are in 'dup_vals'. This preserves increasing index order without sorting and uses only sets and enumerate.
- Time complexity: O(n)
- Space complexity: O(u) additional space for sets, where u is the number of unique values; plus O(k) for the output indices where k is the number of indices returned