Katkat
Back

Design iterator for sorted union

MongoDBSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design an iterator that merges multiple sorted streams of integers while performing on-the-fly deduplication using minimal extra memory.

Problem Statement

Design a class SortedUnionIterator that takes a list of Iterator[int] objects as input. Each iterator provides a sequence of integers in strictly increasing order. The class should provide an interface to iterate through all unique integers present across all input streams in sorted order.

Implement the following interface:

class SortedUnionIterator:
    def __init__(self, iterators: List[Iterator[int]]):
        # Initialize the iterator logic
        pass

    def has_next(self) -> bool:
        # Returns true if there is another unique element
        pass

    def get_next(self) -> int:
        # Returns the next unique integer in ascending order
        pass

Constraints

  • The input streams are strictly increasing.
  • You must not load all elements into memory at once.
  • The space complexity should be O(k), where k is the number of iterators.

Examples

Example 1: Input: iters = [[1, 3, 5], [2, 3, 6]] Output: [1, 2, 3, 5, 6] Explanation: The iterators are merged and duplicates are removed during iteration.

Edge Cases

  • Empty list of iterators.
  • Iterators of different lengths.
  • Iterators containing no elements.
  • All iterators having identical elements.

Hints

Hint 1

Use a min-heap to keep track of the current head element of each iterator.

Hint 2

Store the value and the index of the iterator it originated from in the heap.

Hint 3

When extracting the minimum element, check if it equals the last returned element to skip duplicates.

Follow-up questions

  • How would your implementation change if the input iterators contained duplicates within themselves?
  • What is the time complexity of the `get_next` operation in terms of k (number of iterators)?
  • How would you handle the scenario where the number of iterators is extremely large (e.g., millions)?