Duplicate ticket IDs before the print run
A local council sells tickets for its summer festa through a small Python program. Each ticket has an eight-character alphanumeric ID. The council has 48,000 ticket records in a CSV file and needs a nightly check for duplicate IDs before printing. The current function compares every record with every other record using two nested loops. On the office PC it takes 6 minutes 40 seconds; the council wants the check to finish in under 5 seconds because it must run before the 23:30 print job. A student proposes either sorting the list and comparing adjacent IDs, or putting IDs into a Python set and comparing lengths. The CSV is unsorted and contains a few blank IDs and some lowercase IDs that were keyed manually. The council cannot change the ticket system that produces the CSV, and the office PC has 8 GB RAM.
1. Explain why the nested-loop check is too slow, and compare the two proposed alternatives in terms of time complexity, memory use and suitability for this task.
Read the worked answer
The nested loop performs about n(n−1)/2 comparisons: 48,000 × 47,999 / 2 ≈ 1.15 billion. In CPython each comparison also carries loop and indexing overhead, which explains the 400 seconds. This is O(n²), so the time grows roughly fourfold if the file doubles.
Sorting is O(n log n): about 48,000 × 15.6 ≈ 750,000 comparisons plus the sort's own overhead, followed by one O(n) scan for adjacent equal IDs. A set is O(n) expected: 48,000 insertions, then a length comparison; it stores roughly 48,000 entries in a hash table, a few megabytes, well within 8 GB. The set is the best fit for a fast yes/no nightly check. Sorting is preferable if the council wants a printed list of duplicate IDs in order, because duplicates end up adjacent.
Both need normalisation first: strip whitespace and uppercase each ID, and decide whether blank IDs are errors or should be ignored. Otherwise ' ab1234 ' and 'AB1234' will not be recognised as the same ID, and the check will miss a real duplicate.
2. The student's check is len(ids) != len(set(ids)). Explain exactly what this detects and what it does not, then give an O(n) approach that produces the list of duplicated IDs.
Read the worked answer
len(ids) != len(set(ids)) answers only 'is there at least one duplicate?'. It does not say which IDs are duplicated, how many times, or which rows need correcting. A repeated blank ID will also trigger it. Because the set collapses equal values, all information about which value repeated is lost.
A direct O(n) approach keeps a seen set and a duplicates set:
seen = set() dupes = set() blank_count = 0 for raw in ids: key = raw.strip().upper() if not key: blank_count += 1 continue if key in seen: dupes.add(key) else: seen.add(key)
This is O(n) expected time and O(n) memory, and returns an actionable list. If the council needs counts per ID, use a dictionary or collections.Counter instead. Blank IDs should be reported separately because they are a data-quality problem, not a duplicate ticket in the normal sense.
3. Describe a set of tests that would give confidence in the new duplicate check before it replaces the old one.
Read the worked answer
Test correctness on small, controlled inputs: an empty list; all unique IDs; one duplicated pair; three copies of the same ID; duplicates that differ only by case or surrounding spaces; blank and whitespace-only IDs; and duplicates at the first and last positions. Each test should have a known expected duplicate list, not merely a pass/fail flag.
Test performance and scale with a generated 48,000-row file containing a known number of duplicates, and time it on the office PC against the under-5-second requirement. Test the real CSV and manually verify a sample of the reported duplicates. Also test how the program behaves when the file is missing, has a header row, or contains non-ASCII characters, because an unhandled exception at 23:29 is worse than a slow check. Keep the old slow implementation available to cross-check the new one on a smaller extract; if both agree on the same duplicate set, confidence is much higher.