Union of Two Sorted Iterators

Implement a UnionIterator class that takes two iterators, each already sorted in ascending order, and exposes a single iterator over their union in globally ascending order.

class UnionIterator:
    def __init__(self, it1, it2): ...
    def has_next(self) -> bool: ...   # is there another element?
    def next(self) -> int: ...        # return the current smallest element and advance the underlying iterator

• Method names vary with the language: has_next / next in Python, hasNext / next or hasNext / getNext in Java/C++.
• Lazy evaluation is required. Do not read all input up front; pull the next element from an underlying iterator only when it is needed. Brute force (drain both, sort, replay) is explicitly ruled out, and memory use should be minimal.
• Duplicates across the two iterators must be removed — the output contains no repeated values.
  • Minority variant: some versions state only the merge-in-order requirement with no mention of de-duplication — clarify before coding.

• The bar is high on code quality, coding speed and test coverage. Candidates who reached the clean two-head solution have still been rejected, so a merely correct answer is not enough — write tidy code and walk through test cases yourself.
• has_next() must not consume elements. Keep the "peeked" head separate from the underlying iterator so repeated has_next() calls are idempotent.
• De-duplication has to cover equal values that appear at the same time on both sides, and (depending on the clarified spec) repeats within one iterator.
• Exhaustion edge cases: one iterator empty from the start, one running out mid-stream, and next() called when nothing is left.
• In C++, the problem plays out quite differently from the versions in common prep write-ups. A candidate interviewing in C++ found that preparation did not carry over and got stuck — practice it in the language you will interview in.

• Write the two-iterator version with peek caching and de-duplication in your interview language in under 15 minutes, then write its tests (empty inputs, all-equal inputs, interleaved inputs, one side exhausted).
• Extend it to K iterators with a min-heap and state the per-call complexity.
• Practice explaining has_next idempotency and why buffering everything violates the lazy-read requirement.