Citadel·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Citadel Data Scientist technical screen, one meaty Python generator question that took up the whole session. Harder than I expected for a DS role, felt more like a software engineering interview.

Questions Asked (1)

Write a Python generator called merge_unique(a, b) that lazily merges two non-decreasing iterables (potentially infinite) into one sorted stream with duplicates removed, using only yield and built-ins. You need to prove laziness with a minimal example, handle unbounded inputs without pre-buffering, and avoid quadratic behavior on long runs of equal elements. Include unit tests covering correctness and laziness.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This wrecked me a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: lazy merge of two sorted iterables with deduplication, handling infinite streams and long runs of duplicates efficiently. Then outline a generator-based solution using iterators and a lookahead buffer, emphasizing O(1) memory and linear time. Finally, demonstrate laziness with a minimal example and provide unit tests that verify both correctness and lazy evaluation.

Pro tip: Use a small lookahead buffer to avoid quadratic behavior on long runs of equal elements, and explicitly test laziness by using infinite iterators and asserting that only the needed elements are consumed.

1. Clarify requirements and constraints

Restate the problem: merge two non-decreasing iterables lazily, remove duplicates, handle infinite inputs, and avoid quadratic behavior on long runs of equal elements. Mention that only yield and built-ins are allowed.

2. Design the generator algorithm

Use iterators for both inputs and maintain a lookahead value for each. At each step, compare the current values, yield the smaller one if it's new (not equal to the last yielded), and advance the corresponding iterator. Handle exhaustion gracefully.

3. Implement the generator with yield

Write the merge_unique function using a while loop and yield. Use a variable to track the last yielded value to skip duplicates. Ensure that only one element is consumed from each iterator at a time to maintain laziness.

4. Prove laziness with a minimal example

Show that the generator only consumes elements as needed. For example, use an infinite iterator (like itertools.count) and demonstrate that taking the first few elements works without hanging.

5. Write unit tests for correctness and laziness

Include tests for: merging finite sorted lists with duplicates, handling empty inputs, merging infinite streams (using islice), and verifying that the generator does not pre-buffer by checking consumption counts.

Key Points to Mention

Use of iterators and next() to pull elements lazily from both inputs.
Maintaining a lookahead buffer (one element per iterator) to compare and advance without pre-buffering entire streams.
Deduplication by tracking the last yielded value and skipping equal elements.
Handling infinite iterables by never exhausting them prematurely and using islice in tests.
Avoiding quadratic behavior on long runs of equal elements by advancing iterators in a single pass.
Unit tests that assert laziness, e.g., using a custom iterator that raises if consumed too far.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.