Coding questions · Amazon
Implement streaming k-way merge with constraints
This question evaluates competence in streaming algorithms and resource-constrained algorithm design, specifically implementing a k-way merge over blocking, potentially unbounded integer iterators while preserving stable duplicates and reasoning about time and O(k) space complexity.
Implement a function merge_k(iterators, N) that returns the first N items of the global ascending order from k sorted, potentially unbounded iterators of integers. Constraints: iterators may block, memory must be O(k), and duplicates must be preserved but made stable by source index (stable tie-breaker). Specify time complexity, show how you would handle iterator exhaustion, and discuss how to add deduplication (unique-only) without increasing asymptotic complexity. Provide unit tests that cover k=1, empty streams, large N, and pathological inputs (e.g., one iterator far slower than the rest).
Streaming K-Way Merge First N Items
Given finite sorted streams, return the first N globally sorted items preserving duplicates and breaking ties by source index.
Examples
Example 1
Input: ([[1,4,7],[1,3,5],[2,6]], 6)
Output: [1, 1, 2, 3, 4, 5]
Explanation: Tie broken by source index while preserving duplicates.
Example 2
Input: ([[], [2,3]], 5)
Output: [2, 3]
Explanation: Empty stream.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.