Coding questions · Citadel
Implement lazy unique-merge generator for sorted streams
This question evaluates knowledge of lazy evaluation, Python generators/iterators, merging nondecreasing streams with duplicate elimination, and considerations of time and space complexity in streaming contexts.
Write a Python generator merge_unique(a, b) that lazily merges two nondecreasing iterables a and b (potentially infinite) into a single nondecreasing stream with duplicates removed, using only yield and built-ins. Requirements: (1) Consume from each input only as needed (prove laziness via a minimal counterexample). (2) Handle unbounded inputs like an arithmetic progression generator; must not pre-buffer entire streams. (3) Avoid quadratic behavior when long runs of equal elements occur. (4) Include unit tests demonstrating correctness and laziness.
Lazy Unique Merge of Two Sorted Iterables
Return the unique sorted merge of two finite nondecreasing iterables. The production version can yield lazily; this exact-match version returns a list.
Examples
Example 1
Input: ([1,2,2,5], [2,3,5,6])
Output: [1, 2, 3, 5, 6]
Explanation: Merge and remove duplicates.
Example 2
Input: ([], [1,1,2])
Output: [1, 2]
Explanation: One empty input.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.