Implement left join on Python lists, no packages
Company: Citadel
Role: Data Scientist
Category: Data Manipulation (SQL/Python)
Difficulty: medium
Interview Round: Technical Screen
Implement a left join in pure Python (no external packages, no pandas). Input: left = list of dicts with key 'id' and arbitrary other fields; right = list of dicts with key 'id' and fields to append (disjoint names from left). Requirements: (1) Preserve the original order of 'left' and left duplicates. (2) Support one-to-many matches on 'right' (i.e., duplicate 'id's): emit one output row per matching right row; if no match, emit a single row with right fields set to None. (3) Time O(n + m) and extra space O(n + m) by using hashing; explain how you would reduce memory when m is huge (e.g., streaming or external sort). (4) Handle missing 'id' keys robustly. Provide clear function signatures and tests on small examples.
Overview: This question evaluates a candidate's ability to implement SQL-style left join semantics using pure Python lists and dictionaries, testing skills in hashing, handling duplicate and missing keys, and reasoning about algorithmic time and space complexity.
Read the full Citadel Data Scientist interview experience this question came from
You are given two tables that represent two lists of records:
- `left_records`: the primary list. It contains an `id` (which may be NULL) and other fields.
- `right_records`: the lookup list. It also contains an `id` (which may be NULL) and fields to append to the left.
Write a SQL query that performs a LEFT JOIN of `left_records` to `right_records` on `id` with the following requirements:
1) Preserve the original order of rows from `left_records` using `left_seq` (and preserve duplicates in `left_records`).
2) Support one-to-many matches on `right_records` (i.e., multiple rows in `right_records` can share the same `id`). For each `left_records` row, return one output row per matching `right_records` row.
3) If a `left_records` row has no matching `right_records` row (including when `left_records.id` is NULL), return exactly one output row with the right-side columns as NULL.
4) Handle missing IDs robustly: rows where `left_records.id` is NULL should not match anything (even if `right_records.id` is NULL).
Return these columns: `left_seq`, `id`, `left_name`, `right_attr`.
Order the final output by `left_seq`, and for rows with multiple matches, order by `right_seq`.
Tables
left_records(left_seq INT, id INT, left_name VARCHAR(50))
right_records(right_seq INT, id INT, right_attr VARCHAR(50))
Hints
- A LEFT JOIN will keep all rows from the left table and produce NULLs on the right when there is no match.
- If the right table has duplicate IDs, a normal join naturally returns one output row per matching right row.