The 38-Minute Seating Script
The exams office at a polytechnic runs a Python script to seat 8,400 candidates across 210 rooms for five sessions. The script sorts the students by student number, then for each student scans every already-seated candidate in each candidate room to check for a course clash before appending. A full run now takes 38 minutes on the office laptop, and the exams officer has started running it overnight. After the last session two defects surfaced: room 114, which has exactly 40 seats, was issued 41 seat labels; and in the printed register student 1000 appeared before student 999, which changed the room-assignment order and pushed three candidates into the wrong room. Nobody noticed either defect until after the papers had been distributed. The officer wants both fixed before the resit session in six weeks, and asks whether the runtime can be cut without touching the clash rule, which the academic board has approved and will not reopen.
1. Explain why the runtime grows so quickly, and propose a data-structure change that reduces the cost of the clash check. State the resulting complexity and say what the change does not fix.
Read the worked answer
Where the time goes. For each of the ~8,400 candidates the script loops over up to 210 candidate rooms and, inside that loop, scans the ~40 candidates already seated in each room. That is roughly 8,400 x 210 x 40, about 70 million string comparisons per session, and string equality on course codes is not free. The growth is quadratic in cohort size: double the students and the run roughly quadruples, which is why 38 minutes appeared 'suddenly' after intake grew.
The change. Per room, keep a hash set of the course codes already seated instead of the candidate list, so the clash check becomes an O(1) membership test and the inner scan collapses to about 8,400 x 210, roughly 1.8 million lookups. Better still, keep a global dictionary mapping course code to the set of room IDs that already hold it, so a candidate only inspects rooms that actually contain a classmate; that is close to linear in the number of students. Normalise the keys first (code.strip().upper()), or the script will silently allow a clash between 'CS101' and 'cs101 '.
What it does not fix. Neither the 41st seat label nor the 999/1000 ordering; both are logic defects that survive any speed-up. Also note that replacing the candidate list may change room-choice order, so the regression test must compare against a fixed expected output rather than against whatever the old script produced last time.
2. Diagnose the two correctness defects, explain why neither was caught before the papers went out, and describe the test that would have caught each.
Read the worked answer
Defect 1: the 41st label. The seat loop is almost certainly range(1, capacity + 1) applied to a zero-indexed structure, or <= where < was intended, so a 40-seat room emits 41 labels. The tell is that it only bites on rooms that end up exactly full, which is why it survived: most rooms are not full, and the code was probably tested with three rooms and ten students. This is a boundary condition, not a random bug. One assertion, len(labels) == room.capacity for every room in every session, catches it permanently.
Defect 2: 1000 before 999. sorted(key=lambda s: s.student_no) sorts strings lexicographically, where '1' < '9', so '1000' lands before '999'. The fix is key=int or zero-padding to a fixed width. Two traps: a student number with a letter suffix breaks int(), so a natural-sort key is safer; and fixing the sort deliberately changes assignment order, so the three misplaced candidates are evidence that seat assignments are not reproducible across versions, not a new bug introduced by the fix.
Why nobody saw it. The register printed, the totals matched, and every individual room looked plausible. There was no invariant check and no golden output to diff against. The dangerous property of a seating bug is that a wrong assignment looks exactly like a right one on paper.
3. The officer wants everything fixed in one change. Rank the three fixes by risk and describe how you would sequence and verify them.
Read the worked answer
Ranking, by severity multiplied by fix risk.
- Off-by-one (highest severity, lowest risk). It can seat a candidate in a room with no chair, which is a fairness and safety issue in a real examination. The change is a character and a boundary test, and the only output difference is a label that should not exist.
- Sort key (medium severity, medium risk). It misplaces a small number of candidates, but the correct fix deliberately changes the assignment output, so the timetable has to be regenerated and re-communicated to invigilators rather than patched quietly.
- Performance refactor (lowest severity, highest risk). Nothing is wrong with the answer today except that it takes 38 minutes, and a rewritten clash checker can silently change who sits where. A fast wrong answer is worse than a slow right one.
Sequencing. Capture a golden output from the current script on a fixed synthetic cohort first, so every later difference is explainable. Ship fixes 1 and 2 together with the boundary and sort tests, and confirm the diff contains only the three sort-affected candidates and the removed label. Then do the performance change as a separate commit and diff against the same golden file. Keep the old script available through the resit week, and tell the officer plainly that a faster run does not alter the board-approved clash rule, because that is the worry behind the question.