What the Night Changed

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

Domain
Python
Difficulty
hard
Seniority
L5
Asked in
Amazon

Problem

A nightly job dumps a dimension table to a list[dict] and hands you two of them: old_snapshot from yesterday's run and new_snapshot from today's, where each row carries an id_field key that identifies it across runs. Return a dict that splits the differences into inserts (ids seen only today), deletes (ids gone since yesterday), and updates (ids present in both runs whose other fields moved), with every bucket sorted by id_field ascending.

Two photographs of the same table, a day apart. Account for everything that moved.

Example

Input:

id_field = "id", new_snapshot = [{"id":1,"dept":"Product","name":"Alice"},{"id":3,"dept":"Eng","name":"Carol"},{"id":4,"dept":"Eng","name":"Dave"}], old_snapshot = [{"id":1,"dept":"Eng","name":"Alice"},{"id":2,"dept":"Sales","name":"Bob"},{"id":3,"dept":"Eng","name":"Carol"}]

Output:

{"deletes":[{"id":2,"dept":"Sales","name":"Bob"}],"inserts":[{"id":4,"dept":"Eng","name":"Dave"}],"updates":[{"new":{"id":1,"dept":"Product","name":"Alice"},"old":{"id":1,"dept":"Eng","name":"Alice"}}]}

Worked solution and explanation

What this really is

Strip the data-warehouse costume and this is a keyed set difference across two collections. Three buckets fall straight out of comparing the id sets: today's ids minus yesterday's are inserts, yesterday's minus today's are deletes, and the overlap is the only place an update can hide. Almost everyone gets that far. What separates candidates is the overlap: you still have to compare the full rows and emit only the ones that actually moved, and you have to do it without an O(n*m) scan. Reach for a nested loop matching ids against ids and you have quietly turned a linear diff into a quadratic one that dies on a real table.

Walking it through

Step 1: Index both snapshots by their id

Walk each list once into a dict keyed by id_field. Now any id resolves to its row in constant time, and the id sets are simply the dict keys. This single move is what keeps the whole diff linear instead of quadratic.

Step 2: Let the id sets carve the buckets

new_keys - old_keys are ids that only showed up today: inserts. old_keys - new_keys vanished overnight: deletes. The intersection old_keys & new_keys is the only candidate pool for updates. A set has no order of its own, so sort each key set before you materialize rows; that is what makes the buckets come out ascending instead of in whatever order the hash table happens to hold them.

Step 3: Filter the overlap down to real changes

An id living in both snapshots is not automatically an update. Compare the two rows and emit {'old': old_row, 'new': new_row} only when they differ; otherwise the record is unchanged and belongs nowhere. The ids already match, so whole-dict equality compares exactly the other fields in one step.

The solution

Snapshot diffing with set operations for CDC
def detect_changes(id_field, new_snapshot, old_snapshot):
    old_index = {}
    for record in old_snapshot:
        old_index[record[id_field]] = record
    new_index = {}
    for record in new_snapshot:
        new_index[record[id_field]] = record
    old_keys = set(old_index.keys())
    new_keys = set(new_index.keys())
    inserts = []
    for k in sorted(new_keys - old_keys):
        inserts.append(new_index[k])
    deletes = []
    for k in sorted(old_keys - new_keys):
        deletes.append(old_index[k])
    updates = []
    for k in sorted(old_keys & new_keys):
        if old_index[k] != new_index[k]:
            updates.append({'new': new_index[k], 'old': old_index[k]})
    return {
        'inserts': inserts,
        'deletes': deletes,
        'updates': updates,
    }

Common follow-up questions