Allocating revision sessions at Westfield College
Westfield College has 620 students preparing for 14 subjects. In the final week, 18 revision sessions run in five rooms across two 90-minute slots. Each student chooses up to three sessions. Some sessions are capped at 30; the most popular has 210 requests. Teachers mark 90 students as priority because they are below target. The current spreadsheet allocates places first-come-first-served and produces clashes: 84 students are booked into two sessions in the same slot, and 37 priority students get no place. The deputy head wants an algorithm that assigns every student to at most one session per slot, respects room capacity, gives priority students first refusal, and is fair to everyone else. The output must list each student's sessions and a waiting list per session. There are 620 student records, each with an ID, subject choices, priority flag, and up to three ranked preferences.
1. Design an algorithm to allocate places. State the data structures and the order of operations, and explain how it handles the constraints.
Read the worked answer
Represent each session as an object with id, slot, room capacity, and an ordered list of assigned students. Represent each student with id, priority flag, and ranked preferences. Use a deferred-acceptance (Gale–Shapley) style algorithm: each student proposes to their first-choice session; each session tentatively keeps up to capacity, ranking students first by priority flag, then by a random tie-break seed, and rejects the rest. Rejected students propose to their next preference, but before proposing, the algorithm checks the student's already-assigned slot set; a session in a conflicting slot is skipped. Repeat until no student has an unchecked preference or all lists are exhausted. Any student not assigned goes to a waiting list for their highest-ranked session that has a queue. This handles capacity, priority, ranked preferences, and slot conflicts, and it is fair because non-priority students compete on the same random seed rather than on who clicked first. The random seed must be recorded so the result can be reproduced.
2. Explain why first-come-first-served produced 84 clashes and 37 priority students without places. Include what the algorithm must check that the spreadsheet did not.
Read the worked answer
First-come-first-served only checks whether a session has a free seat at the moment of booking. It does not check the student's other bookings, so a student can take two sessions in the same slot; that explains the 84 clashes. It also does not reserve capacity for priority students, so a priority student who submits late finds the popular session full; that explains the 37 priority students without a place. The spreadsheet probably allowed manual overtyping and had no transaction, so two staff members could assign the last seat twice. The new algorithm must check, in order: student exists and has not already been assigned in that slot; session capacity is not exceeded; the student's preference rank; and the priority flag at the session's ranking stage. It must also write the assignment and the waiting-list position atomically, so a crash cannot leave a half-booked student.
3. Give three test cases, including edge cases, and the expected result.
Read the worked answer
Test 1, capacity boundary: a session with capacity 30 receives 31 non-priority requests. Expected: 30 assigned, one on the waiting list at position 1, and no student assigned twice. Test 2, slot conflict in a greedy version: a student already holds session A in slot 1, then requests session B also in slot 1. Expected: B is rejected and the student keeps A. Test 3, priority: 30 priority and 5 non-priority students request the same session with capacity 30. Expected: all 30 priority students assigned, and the non-priority students waitlisted in random-seed order. Test 4, exhausted preferences: a student's three sessions are all full. Expected: the student is placed on the waiting list for their first preference, not silently dropped. Test 5, invalid input: the import contains the same student ID twice. Expected: validation rejects the duplicate row and reports it before allocation begins.