Junior Programmer: The export that takes 42 seconds and keeps the wrong email

The export that takes 42 seconds and keeps the wrong email

A marketing team runs a Python export every morning. subscribers holds 20,000 emails in send order. suppressed holds 60,000 addresses. The current code iterates over subscribers and, for each one, does if email in suppressed: and then if email in already_sent: before appending to the output. It takes 42 seconds; the team wants under 3 seconds on the same machine. Emails arrive with mixed case and occasional surrounding whitespace, for example ' [email protected] '. The same person can appear twice in different case, and the current code sends to both. The output must preserve send order, keep the first occurrence's original text (the team reports on it), drop any address whose trimmed, lowercased form is in suppressed, and print a count of duplicates removed. suppressed is also mixed case.

1. Explain where the 42 seconds go and give the data-structure change, with complexity reasoning for the before and after.

Read the worked answer

Both membership tests are linear scans. email in suppressed walks up to 60,000 strings, and email in already_sent walks a list that grows toward 20,000. Total work is roughly 20,000 × (60,000 + average 10,000) ≈ 1.4 billion comparisons. Python string comparison is fast, which is why it is 42 seconds rather than 42 minutes, but the shape is O(n·m) and no micro-optimisation will reach 3 seconds.

Fix: build hash sets once, before the loop, then do O(1) average membership.

suppressed_set = {e.strip().lower() for e in suppressed}
seen = set()

The loop becomes O(n) with a constant factor dominated by strip().lower() per email, which is itself O(length). The whole run is then dominated by 20,000 normalisations plus set lookups, comfortably inside 3 seconds. The same reasoning applies in other languages: list.contains in Java, array.includes in JavaScript, and in on a Python list are all linear, while a hash-based structure is not. The key judgement is that 60,000 is large enough that the constant-factor argument for a linear scan no longer holds.

2. Write the dedupe and filtering loop, and explain why `list(dict.fromkeys(emails))` is not sufficient here.

Read the worked answer

dict.fromkeys deduplicates the exact strings you give it and keeps first-seen order, but it can only key on what you pass in. To apply case-insensitive matching you would have to pass the normalised form, and then the output contains [email protected] rather than the first occurrence's original [email protected]. The requirement is first occurrence's original text, so the mapping must be kept explicitly.

suppressed_set = {e.strip().lower() for e in suppressed}
seen = {}          # normalised -> first original text
out = []
dupes = 0
for raw in subscribers:
    key = raw.strip().lower()
    if key in seen:
        dupes += 1
        continue
    if key in suppressed_set:
        seen[key] = raw      # mark as seen either way
        continue
    seen[key] = raw
    out.append(raw)
print(f'duplicates removed: {dupes}')

Decision point: should a suppressed address count as 'seen'? If it does not, a suppressed copy followed by a non-suppressed copy would send to the second one, which is a compliance problem. Marking suppressed addresses as seen makes suppression sticky, which is the safer default; make the choice explicit in a comment and a test. Also confirm whether a duplicate is counted when both copies are suppressed, since that changes the reported number.

3. List the test cases that pin down the specification, including the ones that would catch a plausible but wrong implementation.

Read the worked answer

Use a small fixture and assert exact output text, exact order, and the duplicate count.

Same address twice with different case and whitespace: output has the first original string only, dupes == 1. Catches a set-only dedupe that keeps the last or lowercase form, which a set implementation would fail.
Suppressed entry differing only by case and surrounding spaces: the subscriber is dropped. Catches comparing raw strings without normalisation, the most common version of this bug.
A suppressed copy followed by a clean copy of the same address: assert it is still dropped. This pins the 'suppression is sticky' decision; a naive implementation that only records accepted addresses into seen re-sends.
Order: a case where alphabetical and input order differ, so a test that sorts still passes is not good enough. Assert the list equality, not the set equality.
Empty inputs: no subscribers, no suppressed. Guards against KeyError/IndexError branches added later.
Performance guard on realistic sizes (20,000 × 60,000) with a generous ceiling of ~5 seconds. It should fail on the O(n·m) version and pass on the set version, which is the regression signal the team actually needs.