# No One Left Behind > Every record stays; fill the gaps where a match exists. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L4 ## Problem You're reconciling two exported tables given as lists of dicts, `left` and `right`, that share a `key` field: combine them the way a SQL left join does, keeping every `left` record and merging in the fields of the first `right` record that shares its `key`. Every output row must expose the same right-side columns (every field name appearing anywhere in `right`, except the join `key`), so an unmatched row, or a match that lacks one of those fields, carries `None` there. ## Worked solution and explanation ### What this really is Strip the SQL costume and the load-bearing move isn't the match, it's the schema. The naive read is that each output row's right-side columns come from its own matched record: unmatched rows get nothing, matched rows get whatever fields their match happened to carry. That passes the easy cases and produces a ragged result where row 1 has a `score`, row 2 has a `badge`, and row 3 has neither. A real left join gives every row the SAME columns: the union of every field name across `right`. To pull that off you have to collect that union BEFORE you merge a single record, then fill it on every row, from the match where the field is present and `None` everywhere else. Two right records with different fields is exactly where a copy-the-match solution quietly falls apart. Rescanning `right` for every left row is the other tell: index it once by key so the join is one linear pass, not O(n*m). --- ### The two-solution split **Copy-the-match (ragged)** For each left row, copy only the fields its own match carried. A row that matched a `{score}` record gets `score`; a row that matched a `{badge}` record gets `badge`; an unmatched row gets neither. Every row can end up with a different column set. **Union schema (uniform)** Collect the union `{score, badge}` from the whole right list first. Every row exposes both columns: filled from the match where present, `None` where the match (or the row) has nothing. One fixed schema across the entire output. --- ### Break down the requirements #### Step 1: Index the right side and collect its column union Walk the right list once. Build a dict mapping each record's key value to the record, keeping the FIRST one when a key repeats. In the same pass, collect the union of right-side column names: every field seen across every right record, minus the join key. This union is the schema every output row will carry. #### Step 2: Give every row the union schema For each left record, copy its own fields into a fresh dict, then look up its key in the index. Now walk the union: for each right column, write the match's value if the match exists and has that column, otherwise write None. Because you fill from the union rather than from the match's fields, matched and unmatched rows come out with identical columns. --- ### The solution **Hash-indexed left join with uniform None fill** ```python def left_join(left, right, key): right_index = {} right_columns = [] seen = set() for record in right: if record[key] not in right_index: right_index[record[key]] = record for column in record: if column != key and column not in seen: seen.add(column) right_columns.append(column) result = [] for left_record in left: joined = dict(left_record) match = right_index.get(left_record[key]) for column in right_columns: if match is not None and column in match: joined[column] = match[column] else: joined[column] = None result.append(joined) return result ``` > **Time and Space Complexity** > > **Time:** O(n + m) where n is the left size and m is the right size. Building the index and collecting columns is O(m); the join pass is O(n) times a small constant for the column union. > > Space: O(n + m) for the index, the column union, and the result. > **Interviewers Watch For** > > Whether the same columns show up on matched and unmatched rows when the right list is heterogeneous. Hand a candidate a right list where one record has `score` and another has `badge`, then check an unmatched row: a copy-the-match solution leaves it bare, and a matched row only carries its own field. A candidate who collected the union up front fills both columns on every row. > **Common Pitfall** > > Taking each row's right-side columns from its own match instead of from the union. It looks correct on homogeneous data, then produces a ragged schema the moment two right records carry different fields, which is exactly the case that breaks the next stage of the pipeline. Collect the union before you merge anything and the raggedness disappears. --- ## Common follow-up questions - How would you handle duplicate keys on the right side? _(Tests whether you keep the first match, the last, or fan out into multiple output rows per left record.)_ - How would you turn this into an inner join instead? _(Tests trimming to only left records that found a right match and dropping the None-fill branch.)_ - What if both sides have millions of records and the index no longer fits in memory? _(Tests knowledge of sort-merge join as an alternative when the hash index exceeds memory.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/no_one_left_behind) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.