No One Left Behind

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

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.

Every record stays; fill the gaps where a match exists.

Example 1

Input:

key = "id", left = [{"id":1,"name":"Alice"},{"id":2,"name":"Bob"}], right = [{"id":1,"score":90}]

Output:

[{"id":1,"name":"Alice","score":90},{"id":2,"name":"Bob","score":null}]

Example 2

Input:

key = "id", left = [{"id":1,"name":"Ada"},{"id":2,"name":"Ben"},{"id":3,"name":"Cy"}], right = [{"id":1,"score":90},{"id":2,"badge":"vip"}]

Output:

[{"id":1,"name":"Ada","badge":null,"score":90},{"id":2,"name":"Ben","badge":"vip","score":null},{"id":3,"name":"Cy","badge":null,"score":null}]

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
def left_join(left, right, key):
    right_index = {}
    # a dict holds each right-side column once, in first-seen order
    right_columns = {}
    for record in right:
        if record[key] not in right_index:
            right_index[record[key]] = record
        for column in record:
            if column != key:
                right_columns[column] = None
    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

Common follow-up questions