Implement lazy unique-merge generator for sorted streams
CitadelData Scientist · Technical ScreenLast updated
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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.