Design iterator for sorted union

Q: Design iterator for sorted union

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at MongoDB.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MongoDB during technical interviews.

Question

Loading...

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).