Start from brute force
The obvious approach is a nested loop. For each record in a, scan all of b for a record with the same key: no match means removed, a match whose record differs means changed. Then scan a for each record of b to find the added ones. It is correct, because every pair gets compared, and it needs only O(1) extra space beyond the output. But it is O(n · m) time for n and m records: two tables of a million rows each mean about 1012 key comparisons, far too many for what should be a quick check after a migration.
The approach
The insight is that every question here is about a key: is it on one side, the other, or both? So index each side by key once, and every later question becomes a hash lookup instead of a scan. After indexing, a key's category follows from two membership tests and, when it is on both sides, one record comparison.
The reference solution builds ma = {r[key]: r for r in a} and mb the same way. added is every k in mb with k not in ma; removed is every k in ma with k not in mb; changed is every k in ma that is also in mb with ma[k] != mb[k]. Python's dict comparison checks every field and its value, ignoring field order, so an extra field or a changed value both count as a change, as the constraints require. Each list goes through sorted, so the report does not depend on the order the rows arrived in. One consequence of the dict comprehension worth knowing: if a key repeats within one side, the last record wins and the earlier ones vanish silently.
Walk through an example
Trace the first example, keyed by "id", where each step below is one line of the reference solution.
| step | line | what it looks at | result |
|---|
| 1 | ma = {r[key]: r for r in a} | ids 1, 2 from a | {1: {"id":1,"v":"a"}, 2: {"id":2,"v":"b"}} |
| 2 | mb = {r[key]: r for r in b} | ids 2, 3 from b | {2: {"id":2,"v":"B"}, 3: {"id":3,"v":"c"}} |
| 3 | added | 2 is in ma; 3 is not | [3] |
| 4 | removed | 1 is not in mb; 2 is | [1] |
| 5 | changed | only 2 is on both sides; "b" != "B" | [2] |
| 6 | return | the three sorted lists | {"added": [3], "removed": [1], "changed": [2]} |
Complexity
Optimal: O((n + m) · f + K log K) time, where f is the number of fields per record (a dict comparison checks each) and K the size of the largest output list; O(n + m) space for the two indexes. Brute force (nested loops): O(n · m · f) time and O(1) extra space.
Edge cases to test
- An empty side:
reconcile([], [{"id":3},{"id":1},{"id":2}], "id") → {"added": [1, 2, 3], "removed": [], "changed": []}, sorted rather than in arrival order. - Numeric keys of 10 or more: Python returns
[2, 9, 10] for ids 10, 9, 2, but the TypeScript reference returns [10, 2, 9], because JavaScript’s .sort() with no comparator compares numbers as strings. .sort((x, y) => x - y) fixes it for numbers. - Same fields, different order:
{"id":1,"v":"a"} against {"v":"a","id":1} is unchanged in Python, but the TypeScript reference compares with JSON.stringify, which depends on key order, and reports id 1 as changed. - A repeated key within one side: with
a = [{"id":1,"v":"a"}, {"id":1,"v":"b"}], the index keeps only the second record, so against b = [{"id":1,"v":"b"}] the diff is empty and the first record disappears without a trace. - The same id with a different type:
{"id": 1} on one side and {"id": "1"} on the other give added: ["1"] and removed: [1]. Mixing both types on one side makes Python’s sorted raise TypeError. - A record with no
key field raises KeyError in Python; in TypeScript it is indexed under undefined.
Common mistakes
- Nested-loop comparison O(n·m) instead of indexing by key.
- Choosing a non-unique key, so records collide and the diff is wrong.
- Not separating “changed” from “added/removed”, which hides the most important category.
- Comparing only one field, so a record whose other fields drifted during the migration is reported as unchanged.
Follow-ups an interviewer asks next
- Can you report which fields changed, not just which records?
- For each changed key, walk the union of the two records’ field names and emit
{field: [old, new]} for every field whose value differs, with a marker for a field present on only one side. That adds O(f) per changed record, and it is what makes the report actionable: “price went from 10 to 1000 on 3 rows” rather than “3 rows changed”. - What if the tables have billions of rows and do not fit in memory?
- Sort both sides by key (an external sort, or
ORDER BY in each database) and walk them with two cursors like the merge step of merge sort, which needs only constant memory. Alternatively, hash-partition both sides by key into buckets that do fit and diff bucket by bucket. Comparing per-partition checksums first lets you skip the partitions that match, the same idea as the Merkle trees Cassandra uses for repair. - How should duplicate keys be handled?
- Detect them instead of letting the index keep the last record: count keys while building each index and return a fourth category,
"duplicate", listing every key that appears more than once on either side. A duplicate primary key after a migration is usually a bug in its own right, and hiding it inside the diff is worse than reporting it. - How do you avoid false “changed” results?
- Compare a normalized projection, not the raw record. Drop fields that are expected to differ, such as
updated_at or a surrogate id, then normalize types and formats on both sides: numeric strings to numbers, trimmed whitespace, timestamps in UTC, consistent decimal precision. Otherwise the report is full of rows that differ only in representation, and the real changes get lost among them.
Where this shows up
Reconciliation diffs verify a migration, keep two systems in sync, or audit that a pipeline preserved data — “what changed between source and target”. The keyed set-difference is the workhorse behind data-quality checks and any “did we drop or corrupt rows” investigation.
Reference solution
Reference solution — Python
def reconcile(a, b, key):
ma = {r[key]: r for r in a}
mb = {r[key]: r for r in b}
added = sorted(k for k in mb if k not in ma)
removed = sorted(k for k in ma if k not in mb)
changed = sorted(k for k in ma if k in mb and ma[k] != mb[k])
return {"added": added, "removed": removed, "changed": changed}
print(reconcile([{"id":1,"v":"a"},{"id":2,"v":"b"}], [{"id":2,"v":"B"},{"id":3,"v":"c"}], "id"))
# -> {'added': [3], 'removed': [1], 'changed': [2]}
Reference solution — TypeScript
function reconcile(a: any[], b: any[], key: string): { added: any[]; removed: any[]; changed: any[] } {
const ma = new Map(a.map((r) => [r[key], r]));
const mb = new Map(b.map((r) => [r[key], r]));
const eq = (x: any, y: any) => JSON.stringify(x) === JSON.stringify(y);
const added = [...mb.keys()].filter((k) => !ma.has(k)).sort();
const removed = [...ma.keys()].filter((k) => !mb.has(k)).sort();
const changed = [...ma.keys()].filter((k) => mb.has(k) && !eq(ma.get(k), mb.get(k))).sort();
return { added, removed, changed };
}
console.log(JSON.stringify(reconcile([{id:1,v:"a"},{id:2,v:"b"}], [{id:2,v:"B"},{id:3,v:"c"}], "id")));
// -> {"added":[3],"removed":[1],"changed":[2]}