Implement a Lazy Union Iterator Over Two Strictly Sorted Iterators

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: ```text 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 1 | Iterator 2 | Output of `UnionIterator` | | --- | --- | --- | | 2, 4, 6, 8, 10 | 1, 2, 3, 5, 8, 13 | 1, 2, 3, 4, 5, 6, 8, 10, 13 | | apple, banana, orange, tree | apple, tree, zoo | apple, 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 | ```hint 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 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. ``` ### 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? ### What a Strong Answer Covers - A correct merge that removes cross-input duplicates, checked against all four examples including the empty input - Constant extra memory and lazy consumption of the inputs - A `hasNext()` that is side-effect free from the caller's point of view, and defined behavior for `next()` at the end - How the lookahead is represented without confusing "no element" with a legitimate value - Code that is generic over comparable element types - Edge-case tests and the time cost per call ### 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?