Design a Lazy Union Iterator for Sorted Inputs
Company: MongoDB
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
Design a lazy union iterator over two finite ascending integer iterators. The union is a sorted merge that preserves every occurrence, including duplicates, and produces values on demand rather than materializing either input. Specify `UnionIterator(left, right)` with `has_next()` and `next()`, then generalize the same interface to `KWayUnionIterator(iterators)` without prescribing the selection algorithm.
### Constraints & Assumptions
- Each input supports its own `has_next()` and `next()` methods and yields integers in nondecreasing order.
- Repeated calls to the union's `has_next()` must not consume an output value.
- The caller invokes `next()` only after `has_next()` returns true.
- Preserve duplicates. If the two-input iterator has equal values available, return the left value first.
- Do not materialize an input or retain an unbounded prefix; the K-way design may keep bounded state for each input.
### Clarifying Questions to Ask
- Should equal values be preserved or deduplicated, and is deterministic source ordering required for ties?
- What should `next()` do if a caller ignores the precondition and invokes it after exhaustion?
- Can an input be infinite, and may an underlying iterator block or fail while fetching its next value?
### What a Strong Answer Covers
- The state held for each input and an invariant distinguishing buffered from unbuffered values.
- Idempotent `has_next()` behavior and a `next()` transition that consumes exactly one source value.
- Correct handling of empty inputs, exhaustion, duplicates, and deterministic ties.
- A K-way selection design with justified per-output time and total auxiliary space, without preloading the streams.
- Tests that interleave `has_next()` and `next()` calls and exercise skewed lengths and repeated values.
### Follow-up Questions
- How would the design change if the union removed duplicate values?
- How would you propagate an exception from one underlying iterator without corrupting buffered state?
- What backpressure or cancellation behavior would you add for blocking or infinite inputs?
Quick Answer: Design a lazy iterator that merges two sorted integer streams while preserving duplicates and left-first ordering on ties. Ensure repeated availability checks do not consume output, keep buffering bounded, and generalize the contract to any number of sorted iterators.