Card 02/ 08
Apply the Six Steps to Finding a Ticket Scanned Twice
Up to 200,000 scans at a gate and one second to answer: the limits rule out checking every pair before a line of code is written.
The six steps for an unseen problem, applied to one task, let the input limits decide the approach before any code exists. A gate scanner logs ticket numbers in the order people enter, and you must report the first ticket scanned a second time, the sign of a copied ticket. Up to 200,000 scans arrive, each a positive whole number, and the answer should come back in about a second. A useful working figure is about 10⁸ simple steps a second, an order of magnitude rather than a measurement.
Before reading on: of O(n²), O(n log n) and O(n), which fit 200,000 scans in about a second?
O(n log n) and O(n) fit; O(n²) does not. For n = 200,000, n² is 4 × 10¹⁰ steps, around 400 seconds at 10⁸ a second. n log₂ n is about 3.5 × 10⁶ and n itself is 2 × 10⁵, both far inside one second.
Each step below holds what it wrote down for this problem.
Six steps applied to a ticket scanned twice
1. Clarify
There are up to 200,000 scans, so n ≤ 2 × 10⁵. Ticket numbers are positive whole numbers, and repeats are the point of the problem. No scans at all is possible, and so is a log with no repeat; both return none. The answer is the ticket of the earliest scan whose number appeared before it. The limit places the problem in a row of the budget below, which pairs input sizes with the slowest complexity that still fits.
| Largest n | Complexity that fits |
|---|---|
| 10 | O(n!) |
| 20 | O(2ⁿ) |
| 500 | O(n³) |
| 5,000 | O(n²) |
| 10⁶ | O(n log n) or O(n) |
| Larger | O(log n) or O(1) |
200,000 falls in the 10⁶ row, so the target is O(n log n) or better.
2. Work examples
Scans 7 3 9 3: the fourth scan repeats 3, so the answer is 3. The edge case, scans 7 3 9: nothing repeats, so the answer is none.
3. State the brute force
Compare each scan with every scan before it; the first match is the answer. It is correct, and O(n²) in the worst case: with 200,000 scans and no repeat it makes n(n − 1)/2, about 2 × 10¹⁰ comparisons, around 200 seconds. That is hundreds of times over the budget.
4. Find the bottleneck
The inner loop answers one question again and again: has this number been seen? A hash set answers it in O(1) on average, so a single pass costs O(n) time and O(n) extra space. Sorting first would also fit the budget at O(n log n), but sorting loses the order of the scans, and the answer depends on that order, so it needs each ticket paired with its position. The set is simpler.
5. Write
One loop over the scans and one set of tickets seen: if the ticket is in the set, return it; otherwise add it. After the loop, return none.
6. Trace
On 7 3 9 3 the set grows to hold 7, then 3 and 7, then 3, 7 and 9, and the fourth scan finds 3 in it and returns 3. On 7 3 9 the loop ends without a hit and returns none. Both match step 2.
Step 4 took a few sentences because the first three had made the bottleneck plain: the brute force's cost came from one repeated question, and a hash set is the structure that answers it at once. The cost fell from O(n²) to O(n), at the price of O(n) memory for the set.
The budget counts steps, not seconds, because a measured time changes from one run and one machine to the next. An interpreted Python loop manages fewer simple steps a second than compiled Java does, so a solution at the very edge of a row is a reason to choose the faster complexity, not a reason to start timing.
← → move through sections and cards