Citadel·Data Scientist·Technical Phone Screen·Senior

Senior

May 2026

Summary

Citadel Data Scientist interview with a pretty meaty coding problem centered on implementing a left join from scratch in pure Python. No libraries, no shortcuts, and they wanted you to think through complexity and edge cases out loud.

Questions Asked (1)

Implement a left join in pure Python using only built-in data structures. Inputs are two lists of dicts sharing an 'id' key. The function must preserve left-side order, handle one-to-many matches on the right, emit a None-padded row when there's no match, run in O(n + m) time and space via hashing, and gracefully handle rows missing the 'id' key entirely.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

This looked manageable at first and then I kept discovering new constraints.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and edge cases, then outline a hash-based solution that builds a dictionary from the right list to achieve O(n+m) time. Walk through the algorithm step-by-step, emphasizing order preservation and handling of missing 'id' keys, and finally discuss trade-offs and potential optimizations.

Pro tip: Mention that you would use a defaultdict(list) to group right rows by id, and explicitly handle rows without 'id' by treating them as non-matching. Also, note that the output should include all left columns plus right columns, with None for missing right values.

1. Clarify requirements and edge cases

Confirm that the output should be a list of dicts, preserving left order, with right columns padded with None when no match. Ask about handling rows missing 'id' on both sides.

2. Design hash-based approach

Propose building a dictionary mapping id to list of right rows for O(1) lookups. Explain that this gives O(n+m) time and space.

3. Outline algorithm steps

Iterate through right list to build the hash map, skipping rows without 'id'. Then iterate through left list in order, for each row with 'id', look up matches and merge; if no match or missing 'id', emit left row with None for right columns.

4. Discuss merging and output format

Explain how to merge dictionaries: for each match, create a new dict with left row's keys and right row's keys (right overwrites if duplicate keys, except 'id'? clarify). For no match, create dict with left keys and None for all right keys.

5. Analyze complexity and trade-offs

Confirm O(n+m) time and space. Mention that alternative nested loop is O(n*m) and not acceptable. Discuss memory usage and potential improvements like using indices if needed.

Key Points to Mention

Use a dictionary (hash map) to group right rows by id for O(1) lookups.
Preserve left-side order by iterating through the left list sequentially.
Handle one-to-many matches by storing lists of right rows per id.
Emit None-padded rows for left rows with no match or missing 'id' key.
Skip right rows missing 'id' when building the hash map.
Ensure output includes all columns from both sides, with right columns set to None when no match.

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