Katkat

Implement lazy unique-merge generator for sorted streams

CitadelData Scientist · Technical Screen

Last 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.