Implement streaming k-way merge with constraints
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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).
Quick Answer: 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.
Given finite sorted streams, return the first N globally sorted items preserving duplicates and breaking ties by source index.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[1,4,7],[1,3,5],[2,6]], 6)
Expected Output: [1, 1, 2, 3, 4, 5]
Explanation: Tie broken by source index while preserving duplicates.
Input: ([[], [2,3]], 5)
Expected Output: [2, 3]
Explanation: Empty stream.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.