Inner join of two CSV datasets

The task is a relational join written by hand. Treat each CSV as a header row plus rows. The join column can sit at a different position in each file, so first find its index in each header.

Brute force. For every customer row, scan every processor row and compare the key values. This takes O(n · m) comparisons. It is correct and a fine thing to say out loud first. With two files of 100k rows each, it does 10^10 comparisons, so it does not scale.

Hash join (optimal). Build a dictionary from the smaller side's key value to the list of its rows. Then stream the other side once. For each customer row, look up its key. Emit one output row per match: the customer values followed by the processor values. Store a list per key, not a single row. If a key repeats on the processor side, a one-to-one dictionary silently drops rows. This is the most common bug interviewers look for.

Why it works: two rows join only when their key strings are equal, and a hash lookup finds exactly the rows with an equal key. Every customer row is visited once, and for each one every matching processor row is emitted once. So the output is exactly the set of matching pairs.

Invariants:

• Output order follows the customer file. Within one customer row, matches keep the processor file's order. The result is deterministic and easy to test.
• Every output row has len(customer_header) + len(processor_header) fields.
• Rows with no match are dropped (inner join). In the left-join variant they are padded with empty strings.

Parse defensively: strip trailing newlines, skip blank lines, and raise a clear error if the join column is missing from either header or a row has the wrong number of fields.

from collections import defaultdict


def _parse(dataset: list[str]) -> tuple[list[str], list[list[str]]]:
    """Split a CSV dataset (header first) into header and rows."""
    lines = [line.rstrip("\r\n") for line in dataset if line.strip()]
    if not lines:
        raise ValueError("dataset has no header row")
    header = lines[0].split(",")
    rows = []
    for number, line in enumerate(lines[1:], start=2):
        values = line.split(",")
        if len(values) != len(header):
            raise ValueError(f"line {number}: expected {len(header)} fields, got {len(values)}")
        rows.append(values)
    return header, rows


def _key_index(header: list[str], field: str) -> int:
    try:
        return header.index(field)
    except ValueError:
        raise ValueError(f"join field {field!r} not in header {header}") from None


def join_datasets(
    customer_file: list[str],
    processor_file: list[str],
    field: str,
    how: str = "inner",
) -> list[str]:
    """Join two CSV datasets on `field`.

    Returns CSV lines: the combined header, then one line per matching pair,
    with the customer values followed by the processor values. Output order
    follows customer_file, then processor_file within each key.
    how="inner" drops customer rows with no match; how="left" keeps them,
    padding the processor columns with empty strings.
    """
    if how not in ("inner", "left"):
        raise ValueError(f"unsupported join type {how!r}")

    c_header, c_rows = _parse(customer_file)
    p_header, p_rows = _parse(processor_file)
    c_key = _key_index(c_header, field)
    p_key = _key_index(p_header, field)

    # Build side: key -> every processor row with that key (keys can repeat).
    by_key: dict[str, list[list[str]]] = defaultdict(list)
    for row in p_rows:
        by_key[row[p_key]].append(row)

    out = [",".join(c_header + p_header)]
    empty = [""] * len(p_header)
    for row in c_rows:
        matches = by_key.get(row[c_key])
        if matches:
            for match in matches:
                out.append(",".join(row + match))
        elif how == "left":
            out.append(",".join(row + empty))
    return out


if __name__ == "__main__":
    customers = ["cust_id,name,country", "c1,Ada,US", "c2,Lin,SG", "c3,Ola,NG"]
    charges = ["amount,cust_id", "500,c1", "120,c3", "75,c1", "900,c9"]

    assert join_datasets(customers, charges, "cust_id") == [
        "cust_id,name,country,amount,cust_id",
        "c1,Ada,US,500,c1",
        "c1,Ada,US,75,c1",
        "c3,Ola,NG,120,c3",
    ]
    assert join_datasets(customers, charges, "cust_id", how="left")[3] == "c2,Lin,SG,,"
    assert join_datasets(customers, ["amount,cust_id"], "cust_id") == [
        "cust_id,name,country,amount,cust_id"
    ]
    try:
        join_datasets(customers, ["amount,id"], "cust_id")
        raise AssertionError("expected missing field error")
    except ValueError:
        pass
    print("ok")

Let n be the customer rows, m the processor rows, w the row width, and k the number of output rows.

• Parsing: O((n + m) · w) time.
• Building the index: O(m) time and O(m · w) space.
• Probing: O(n) lookups plus O(k · w) to write the output. Total time O((n + m + k) · w).
• k can be as large as n · m when every row shares one key. No algorithm can do better than the size of its output, so the output term is unavoidable.
• The brute force is O(n · m · w) time and O(1) extra space beyond the output.

• Basic inner join, key in different columns: customers cust_id,name,country / c1,Ada,US / c2,Lin,SG / c3,Ola,NG; charges amount,cust_id / 500,c1 / 120,c3 / 75,c1 / 900,c9 → header cust_id,name,country,amount,cust_id, then c1,Ada,US,500,c1, c1,Ada,US,75,c1, c3,Ola,NG,120,c3.
• Unmatched rows on either side (c2, c9) are dropped.
• Duplicate keys on both sides: 2 customer rows and 3 processor rows with key k → 6 output rows.
• Header only in the processor file → output is just the combined header.
• No overlapping keys → only the header.
• Single-column files (id / a and id / a) → id,id, a,a.
• Join field missing from a header → ValueError.
• Row with too few fields → ValueError naming the line number.
• Trailing \n or \r\n on lines and blank lines → ignored.
• Left join: c2 has no match → c2,Lin,SG,, (processor columns empty).

1. Left join. Keep every customer row. When there is no match, pad the processor columns with empty strings. This is the how="left" branch. A right join swaps the arguments. A full outer join also tracks which processor keys were matched, then appends the unmatched processor rows with empty customer columns.
2. Duplicate keys. Already handled by storing a list per key. Expect a question on output size: with skewed keys the result can grow to n · m, so you may need to stream rows out instead of building a list (make the function a generator).
3. Sorted output or sorted inputs. If the output must be ordered by the key, sort the result by the key column. If both inputs arrive already sorted by the key, use a sort-merge join: two pointers walk both files and the matching runs are cross-producted. This needs O(1) extra memory beyond one run, so it works on files that do not fit in memory.
4. Drop the duplicate key column, or prefix columns. Remove the processor's key column from the output, and rename clashing column names (for example processor.amount). Build the output header once and use a list of column indices for each row.
5. Real CSV. Values with quoted commas or embedded newlines break split(","). Switch to the csv module for reading and writing. Also discuss composite keys (a tuple of several fields) and normalising keys (trim, case) before you compare them.

Mid-level (L4)

• Parses the header, finds the key column in each file, and gets a working inner join, even if it starts with nested loops.
• Moves to a dictionary lookup when asked about scale.
• Writes a few tests and handles the empty and no-match cases.

Senior (L5)

• Starts with the hash join, maps each key to a list of rows, and explains why one-to-one is wrong.
• Keeps the output order deterministic, validates the inputs, and adds left join with little change to the code.
• Gives a correct complexity that includes the output size.

Staff (L6+)

• Discusses build-side choice (index the smaller file), sort-merge join for sorted or oversized inputs, and streaming output.
• Brings up real CSV parsing, key normalisation, composite keys, and memory limits without being prompted.
• Structures the code so join types and output options are small, testable variations, not copies.