How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Design iterator for sorted union | MongoDB Coding Question

Design iterator for sorted union

Company: MongoDB

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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

Quick Answer: 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.

Part 1: Sorted Union of Two Increasing Lists

You are given two integer lists a and b. Each list is already sorted in strictly increasing order, meaning each list is sorted and contains no duplicates within itself. Return a new list containing the sorted union of both inputs: every value that appears in either list, in increasing order, with duplicates removed. If a value appears in both lists, it should appear only once in the result. Aim for a linear-time merge-style solution.

Constraints

0 <= len(a), len(b) <= 200000
-10^9 <= a[i], b[i] <= 10^9
Each input list is strictly increasing
An O(len(a) + len(b)) solution is expected

Examples

Input: ([1, 3, 5, 7], [2, 3, 6, 7, 8])

Expected Output: [1, 2, 3, 5, 6, 7, 8]

Explanation: Merge both sorted lists and keep shared values only once.

Input: ([], [1, 2, 3])

Expected Output: [1, 2, 3]

Explanation: Edge case: the first list is empty, so the answer is the second list.

Input: ([1, 2, 3], [])

Expected Output: [1, 2, 3]

Explanation: Edge case: the second list is empty, so the answer is the first list.

Input: ([-5, -1, 4], [-5, 0, 4, 10])

Expected Output: [-5, -1, 0, 4, 10]

Explanation: Shared values -5 and 4 appear once in the result.

Input: ([2], [2])

Expected Output: [2]

Explanation: Edge case: both lists contain the same single value.

Hints

Use two pointers, one for each list, and compare the current values.
When the two current values are equal, add the value once and advance both pointers.

Part 2: Sorted Union of K Increasing Lists

You are given k integer lists, where each inner list is sorted in strictly increasing order and contains no duplicates within itself. Return the sorted union of all values across all lists, including each distinct value only once. Design an efficient solution for large k. Avoid flattening everything and sorting from scratch if possible.

Constraints

0 <= len(lists) <= 100000
0 <= total number of integers across all inner lists <= 200000
-10^9 <= value <= 10^9
Each inner list is strictly increasing
An O(N log k) solution is expected, where N is the total number of values and k is the number of lists

Examples

Input: [[1, 3, 5, 7], [2, 3, 6, 7, 8], [0, 7, 9]]

Expected Output: [0, 1, 2, 3, 5, 6, 7, 8, 9]

Explanation: A heap-based k-way merge produces values in order; repeated values such as 3 and 7 appear once.

Input: []

Expected Output: []

Explanation: Edge case: no lists are provided.

Input: [[], [], []]

Expected Output: []

Explanation: Edge case: all lists are empty.

Input: [[4, 10, 20]]

Expected Output: [4, 10, 20]

Explanation: Edge case: a single list should be returned as-is.

Input: [[-3, 1, 5], [-3, 0, 4], [0, 2, 5], []]

Expected Output: [-3, 0, 1, 2, 4, 5]

Explanation: Duplicates across different lists are removed while preserving overall sorted order.

Hints

Keep the current smallest available value from each non-empty list in a min-heap.
When you pop a value from the heap, compare it with the last value you added to the answer to avoid duplicates.

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.