Exam Room
01 · Problem
An exam hall has one row of n seats numbered 0 to n - 1. Students enter one at a time and each picks the seat that is as far as possible from the nearest occupied seat. If several seats tie for that distance, the student picks the lowest-numbered one. When the hall is empty the student sits in seat 0.
Implement the ExamRoom class:
ExamRoom(int n)sets up a hall withnempty seats.int seat()returns the seat chosen by the next student and occupies it.void leave(int p)frees seatp. Seatpis guaranteed to be occupied.
seat() is only called when at least one seat is free.
02 · Examples
["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
[null,0,9,4,2,null,5]
Seats chosen: 0 (empty hall), 9 (farthest end), 4 (middle of 0..9, lowest on tie), 2 (middle of 0..4). After seat 4 is freed, the gap 2..9 gives distance 3 at seat 5.
["ExamRoom","seat","seat","seat","leave","leave","seat"], [[4],[],[],[],[0],[3],[]]
[null,0,3,1,null,null,3]
Seats 0, 3, then 1 (seats 1 and 2 are both distance 1 from the nearest student; the lower index wins). After 0 and 3 leave only seat 1 is taken; seat 3 is distance 2 away while seat 0 is distance 1, so the student picks 3.
["ExamRoom","seat","seat","seat"], [[5],[],[],[]]
[null,0,4,2]
Seat 0 first, then seat 4 (distance 4), then seat 2, which is distance 2 from both neighbours.
03 · Constraints
- 011 <= n <= 109
- 02At most 104 calls are made to seat and leave
- 03leave(p) is only called when seat p is occupied
- 04seat is only called when a free seat exists
04 · Optimal complexity
- Time
- O(log k) per seat/leave
- Space
- O(k)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.