Setup
No AI for this kata.
A nightly import cleans up a list of customer records. A profiler shows almost all the time is spent in this function:
def dedupe(records):
seen = []
result = []
for r in records:
key = (r["email"].lower(), r["country"])
if key not in seen:
seen.append(key)
result.append(r)
return resultWith 10,000 records (about 30% duplicates), it takes 0.4 seconds. Next month’s import will have 100,000 records, with the same duplicate rate.
After you commit, do the kata itself:
- Explain in one sentence why the time grows the way it does.
- Rewrite
dedupeso it scales linearly, without changing which record is kept for each duplicate. - Run both versions under a profiler at 10,000 and 100,000 records and compare the profiles.
Outcome
About 40 seconds. Anything from 30 to 50 is a good answer.
key not in seen scans a list, so each check gets slower as seen grows. That makes the function quadratic: 10× the records means about 100× the time. With 30% duplicates, seen grows to about 70,000 keys, and each new record is compared against an average of tens of thousands of them.
Changing seen to a set makes each check take constant time, and the whole function runs in a few hundredths of a second at 100,000 records. Same output, about 1,000× faster.
Senior commentary
“When someone gives me one timing and asks about a bigger input, the first thing I do is find the loop inside the loop. in on a list is a hidden loop, and it’s one of the easiest to miss because it reads like a single operation.
“The habit worth building: whenever you see a membership check, ask what the container is. List means linear, set or dict means constant. And a one-line profile at two sizes tells you the growth rate faster than reading the code: if 10× the input costs 100× the time, you have a quadratic.”
Discussion questions
- Did you predict 4 seconds, 40, or something else? What model of the code did that number come from?
- Where else do hidden loops show up? Think of
.index(),.count(), string concatenation, and ORM calls inside loops. - How would you catch this before next month’s import, without a 100,000-row test?