Katkat
Back

Implement a Lazy Union Iterator Over Two Strictly Sorted Iterators

MongoDBSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement a UnionIterator that lazily merges two strictly sorted iterators of integers or strings into one strictly sorted iterator without duplicates, using constant extra memory. Tests iterator protocol design, one-element lookahead, cross-input deduplication, end-of-stream behavior and edge cases such as empty inputs.

Implement a UnionIterator class that takes two iterators, each producing its elements in strictly increasing order, and is itself an iterator with these properties:

  • It produces the union of the elements of both inputs. An element that appears in both inputs is produced only once.
  • Its output is also strictly increasing.
  • It does not use much memory, even when the inputs contain a very large number of elements.

The input iterators follow this interface. UnionIterator takes the two iterators in its constructor and implements the same two methods:

hasNext() -> bool # true if the iteration has more elements
next() -> element # returns the next element in the iteration (an int or a string)

Examples

Iterator 1Iterator 2Output of UnionIterator
2, 4, 6, 8, 101, 2, 3, 5, 8, 131, 2, 3, 4, 5, 6, 8, 10, 13
apple, banana, orange, treeapple, tree, zooapple, banana, orange, tree, zoo
-10, -9, -5, -1, 0, 2, 4-9, -5, -3, -2, 0, 1, 2-10, -9, -5, -3, -2, -1, 0, 1, 2, 4
1, 2, 3(empty)1, 2, 3

Constraints and Clarifications

  • Each input is strictly increasing, so neither input repeats an element on its own.
  • Within one UnionIterator, both inputs hold the same element type: all integers or all strings. Strings compare in ordinary lexicographic order.
  • Either input, or both, may be empty.
  • The inputs may be too long to hold in memory, or produced lazily. Do not copy them into a list or set: extra memory must not grow with the length of the inputs.
  • As with any iterator, hasNext() may be called any number of times between calls to next() and must not change what next() returns.

Clarifying Questions

  • What should next() do when there are no more elements: raise an exception, or return a sentinel?
  • Can an input contain a null element?
  • Should the class trust the strictly increasing guarantee, or detect and report an input that violates it?
  • Will a single thread use the iterator, or must it be safe to share?

Hints

Hint 1

An iterator is not a linked list: With a linked list you can look at a node's value and decide later whether to move past it. An iterator's next() hands you the value and moves on in a single step. Decide what that means when you need to compare the fronts of both inputs.

Hint 2

Check the equal case and the end: Trace the first example by hand at 2 and at 8, where both inputs offer the same value, and again after one input runs out. Make sure hasNext() gives the right answer at each of those points.

Follow-up questions

  • Generalize to k sorted iterators. What is the time per `next()` and the extra memory?
  • Implement an `IntersectionIterator` that produces only the elements present in both inputs.
  • The inputs are only non-decreasing, so each may repeat elements, but the output must still be strictly increasing. What changes?
  • Is your iterator safe if two threads call `next()` concurrently? What would you change to make it safe?