Problem RestatementProblem
Design course registration for a university (asked at JPMorgan). Students browse courses and sections, and register when their registration window opens. Popular sections fill in seconds. If a section is full, students join a waitlist, and when someone drops, the next waitlisted student gets the seat. The system must enforce prerequisites, no schedule conflicts and credit limits. The hardest moment: thousands of students clicking "register" at the same second when registration opens.
RequirementsRequirements
- Browse courses and sections (time, room, instructor, seats left).
- Register and drop. Seat counts must be strictly correct (no over-enrollment).
- Waitlist with fair ordering and automatic promotion.
- Validate prerequisites, schedule conflicts and credit limits.
- Handle huge spikes at window openings.
Data ModelData model
CREATE TABLE sections (
section_id BIGINT PRIMARY KEY, course_id BIGINT, term TEXT,
capacity INT, enrolled INT DEFAULT 0 CHECK (enrolled <= capacity),
meeting_times JSONB -- e.g. [{"day":"MON","start":"10:00","end":"11:15"}]
);
CREATE TABLE enrollments (student_id BIGINT, section_id BIGINT, status TEXT, -- enrolled, dropped
created_at TIMESTAMP, PRIMARY KEY (student_id, section_id));
CREATE TABLE waitlist (section_id BIGINT, student_id BIGINT, position BIGSERIAL, status TEXT, -- waiting, offered, expired
offered_until TIMESTAMP, PRIMARY KEY (section_id, student_id));
CREATE TABLE prerequisites (course_id BIGINT, required_course_id BIGINT);
CREATE TABLE registration_windows (student_group TEXT, opens_at TIMESTAMP); -- seniors first, etc.Register Flow (in one transaction)Flows
- Checks (in memory or cached): the window is open for this student, prerequisites are met (from the transcript), there's no time conflict with current enrollments, and credits stay within the limit.
- Take a seat atomically:
UPDATE sections SET enrolled = enrolled + 1 WHERE section_id = ? AND enrolled < capacity.
- 1 row updated → insert the enrollment and commit. Success.
- 0 rows → the section is full, so offer to join the waitlist.
CHECK (enrolled <= capacity) constraint is a last safety net.
Drop: in one transaction, set the enrollment to dropped and do enrolled - 1. Then trigger waitlist promotion.
Deep Dive — Giving away a seat that just openedDeep dive
A student drops a full section with forty people waitlisted. Who gets the seat, and what if they have stopped paying attention?
Mark the seat open and let people race
The seat count goes up and whoever registers first gets it.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
DROP["Student drops - seat free"] --> OPEN["seats_taken decremented"]
OPEN --> RACE["Anyone can register - waitlisted or not"]
RACE --> FAST["Someone refreshing every 5 s wins"]
RACE --> QUEUE["Position 1, who waited 3 weeks, gets nothing"]
RACE --> BOT["Students write scripts - load spikes on every drop"]The waitlist becomes decorative, and because a freed seat is a race, students build tooling to win it. The system ends up serving a polling storm it created itself.
Promote the first waiting student automatically
On a drop, find the lowest waitlist position and enrol them.
The queue now means something, and this is most of the answer. Two gaps. Enrolling someone automatically can be wrong — three weeks later they may have a timetable clash, be over their credit limit, or no longer have the prerequisite — and if two students drop at the same moment, two promotions can race and enrol the same person twice or overshoot the capacity.
Offer the seat, with a deadline, inside one transaction
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
DROP["Drop"] --> TX["Transaction - lock the section row"]
TX --> NEXT["Take the lowest waitlist position"]
NEXT --> CHK{"Still eligible? - conflicts, credits, prerequisites"}
CHK -->|"no"| SKIP["Skip, record why, take the next"]
CHK -->|"yes"| OFFER["Offer the seat - expires in 24 h"]
OFFER --> ACC{"Accepted?"}
ACC -->|"yes"| ENROL["Enrolled"]
ACC -->|"no / expired"| NEXT- Lock the section row for the promotion. Two simultaneous drops then serialise, so the seat count stays right and nobody is promoted twice.
- Re-check eligibility at promotion time, not at waitlist time. The student's schedule has changed since they joined the queue, and auto-enrolling them into a clash creates a support ticket instead of a solution.
- Offer rather than enrol, with an expiry. Twenty-four hours respects the queue order while guaranteeing the seat does not sit frozen behind someone who has left the university. When it lapses, the same transaction moves to the next position.
Hold the seat as offered for the duration — neither free nor enrolled — so it cannot be taken by the open race and cannot be double-offered. That intermediate state is the piece the earlier rungs were missing.
Surviving the Opening Spike
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
ST["Students"] --> VQ["Virtual waiting room - fair queue"]
VQ --> API["Registration API - stateless, scaled"]
API --> CACHE[("Cached catalog + seat counts - read only")]
API --> DB[("Primary DB - atomic seat updates")]
DB --> EV[("Events: seat freed")]
EV --> WL["Waitlist promoter"]
WL --> DB- Stagger windows by student group (seniors at 8:00, juniors at 9:00, ...). The simplest and most effective control.
- Virtual waiting room: admit students into the registration flow at a controlled rate, in fair (random or arrival) order, and show their position.
- Read vs write split: browsing uses cached catalog and approximate seat counts. Only the "register" action touches the primary DB's atomic update.
- Short transactions: validation happens before the transaction, and the transaction is just the conditional update + insert, which keeps row locks brief.
- Hot sections: many students update the same row. That's fine at this scale (thousands, not millions per second) with short transactions. Load test the exact peak beforehand.
- Idempotency: a double click doesn't double-enroll (the primary key is
(student, section)).
Wrap-UpWrap-up
Model sections with capacity and an enrolled count protected by a CHECK constraint, and register with a single conditional update (enrolled < capacity) plus an enrollment insert in one short transaction, after validating prerequisites, conflicts and credits. Drops trigger fair, transactional waitlist promotion (auto-enroll or a timed offer). Survive the opening spike with staggered windows, a virtual waiting room, cached read-only browsing and idempotent registration.