Design iterator for sorted union
Quick Overview
This question evaluates algorithmic thinking and iterator-based streaming skills, focusing on merging strictly increasing inputs and deduplicating results while maintaining efficient (amortized linear) performance and minimal memory footprint.
Problem: Union Iterator for Sorted Inputs
You are given two input iterators it1 and it2. Each iterator returns integers in strictly increasing order (sorted and no duplicates within the same iterator).
Design a union iterator that iterates over the sorted union of the two inputs, returning each value once (i.e., remove duplicates that appear in both inputs).
Interface
Assume each input iterator supports:
-
boolean hasNext() -
int next()
Implement a UnionIterator supporting the same methods:
-
boolean hasNext() -
int next()
Requirements
- Output must be in increasing sorted order .
- Output must contain no duplicates .
- Time should be efficient (amortized linear in the total number of input elements).
- Use only iterator access (do not convert iterators to arrays/lists).
Example
-
it1: 1, 3, 5, 7 -
it2: 2, 3, 6, 7, 8 - Output: 1, 2, 3, 5, 6, 7, 8
Follow-up
Generalize your design to support the union of k sorted iterators (each individually strictly increasing), producing a sorted de-duplicated union.
Clarify any assumptions you need (e.g., behavior when next() is called with no remaining elements).