Citadel·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Citadel data scientist interview with a coding question that was more algorithmic than I expected. They gave you two tables worth of data as Python dicts and wanted you to implement a left join from scratch, no pandas, no nothing.

Questions Asked (1)

Given two lists of dictionaries representing an orders table and a customers table, write Python code without any third-party libraries to perform a left join on the 'customer' key. Then explain how you'd get the solution down to O(N+M) time using hashing.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was the nested loop approach and I just started coding it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the data structures and join semantics, then implement a straightforward nested-loop left join in pure Python. Next, explain how to optimize to O(N+M) by building a hash map from the customers table keyed on 'customer', and finally iterate through orders to produce the joined result.

Pro tip: Mention that you would handle duplicate keys in the customers table by storing a list of matches, and explicitly discuss the trade-off between memory usage and time complexity when using a hash map.

1. Clarify requirements and data assumptions

Confirm the structure of the lists of dictionaries, the join key, and what should happen when there is no match (e.g., include None or omit). Also ask about duplicate keys.

2. Implement naive nested-loop left join

Write a simple double loop that for each order scans all customers to find a match, producing a new list of merged dictionaries. This is O(N*M) time.

3. Optimize with hashing

Build a dictionary mapping customer key to a list of customer records (to handle duplicates). Then iterate through orders once, looking up matches in O(1) average time, resulting in O(N+M) time.

4. Discuss trade-offs and edge cases

Explain memory overhead of the hash map, handling of missing matches, and potential for collisions (though Python dict handles them). Mention that if one table is much smaller, you might build the hash map on that table.

Key Points to Mention

Left join semantics: all rows from the left table (orders) are kept, with None or missing values for non-matching right table columns.
Hash map construction: key by the join column ('customer'), value as a list of matching customer dictionaries to handle duplicates.
Time complexity: nested loop is O(N*M); hash join is O(N+M) average case due to O(1) dictionary lookups.
Space complexity: O(M) extra space for the hash map, which is a trade-off for improved time.
Edge cases: missing keys, duplicate keys, and ensuring the output format matches expectations (e.g., merging dictionaries).
Python implementation details: using dict.get() for safe lookups, list comprehensions for concise code, and avoiding third-party libraries.

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