Implement lazy unique-merge generator for sorted streams
Company: Citadel
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
Quick Answer: 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.
Return the unique sorted merge of two finite nondecreasing iterables. The production version can yield lazily; this exact-match version returns a list.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,2,5], [2,3,5,6])
Expected Output: [1, 2, 3, 5, 6]
Explanation: Merge and remove duplicates.
Input: ([], [1,1,2])
Expected Output: [1, 2]
Explanation: One empty input.
Input: ([1,1,1], [1])
Expected Output: [1]
Explanation: Long equal run.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.