# What the Night Changed > Two photographs of the same table, a day apart. Account for everything that moved. Canonical URL: 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. ## 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 minus old_keys are ids that only showed up today: inserts. old_keys minus new_keys vanished overnight: deletes. The intersection is the only candidate pool for updates. Sort each key set before you materialize rows and the ascending order falls out for free. #### 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. Whole-dict equality settles it in one comparison. --- ### The solution **Snapshot diffing with set operations for CDC** ```python 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, } ``` > **Trick to solving** > > Stop thinking 'match every new row against every old row.' Think 'compare two id sets, then look up rows by id.' The difference and intersection of the key sets hand you the three buckets directly, and the dict keeps every row access O(1). > **Performance insight** > > **Time:** O(n + m) to index both snapshots, plus O(k log k) to sort the change sets, where n and m are snapshot sizes and k is the number of changes. **Space:** O(n + m) for the two index dicts. > **Interviewers watch for** > > Reaching for set difference and intersection on the keys instead of nested membership loops. It signals you see CDC as a set problem, which is exactly how warehouse merge logic is actually built. > **Common pitfall** > > Comparing rows that hold floats with ==. A value of 10.0 versus 10.000000001 reads as an update when it is really floating-point noise, so a production diff usually compares on a stable hash or rounds first. Nested structures bite the same way. --- ## Common follow-up questions - What if each row carries a last_modified timestamp you can trust? _(Tests optimizing update detection by comparing timestamps instead of full record equality.)_ - How would you handle soft deletes? _(Tests adding a 'deleted' flag instead of removing records from the new snapshot.)_ - How does this scale to millions of records that no longer fit in memory? _(Tests hash-based partitioning: split by key range and process each partition independently.)_ - What is the difference between snapshot CDC and log-based CDC? _(Tests understanding that log-based CDC reads database change logs (WAL) rather than comparing snapshots.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/what_the_night_changed) - [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.