CODING CHALLENGE · N°60

Data Reconciliation Diff

Medium FDEDataIntegrations

The customer swears the migration worked. You reconcile: compare their source records against what landed in the target, keyed by id, and report exactly what was added, removed, or changed. It’s the diff that ends the "it’s not syncing" argument. Solve it in Python or TypeScript, with hidden tests.

The problem

Implement reconcile(a, b, key). a and b are lists of records (dicts) each identified by the field key. Compare them and return {"added": [...], "removed": [...], "changed": [...]} where: added = key values in b but not a; removed = key values in a but not b; changed = key values in both whose records differ. Each list is the sorted key values.

EXAMPLE 1
Input a = [{"id":1,"v":"a"},{"id":2,"v":"b"}], b = [{"id":2,"v":"B"},{"id":3,"v":"c"}], key = "id"
Output {"added": [3], "removed": [1], "changed": [2]}
id 3 is new, id 1 vanished, id 2’s value changed
CONSTRAINTS
  • Index each list by its key field for O(n) comparison.
  • A record is "changed" if the whole record differs (compare the full dicts), not just one field.
  • Return each category as a sorted list of key values.
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement reconcile(a, b, key): build a lookup of key→record for both sides, then compute the three sets — added, removed, changed — and return them sorted.

HINTS — 4 IDEAS
  1. Build two maps: {record[key]: record} for a and for b.
  2. added = keys in b’s map not in a’s; removed = keys in a’s map not in b’s.
  3. changed = keys in both maps whose records are not equal.
  4. Sort each list of keys before returning.
CPython · WebAssembly
Approach, complexity & discussion — open after you solve

The approach

Index both datasets by their key for O(1) lookup, then walk the union of keys and classify each: added (only in the new set), removed (only in the old), changed (in both but values differ), or unchanged. The key-based indexing is what turns a quadratic comparison into a linear one.

Complexity

Time O(n + m) with hash indexes on both sides; space O(n + m).

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.

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.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Challenges