Exam Room

MediumDesigndesign

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

An exam room has n seats in a single row, numbered 0 to n - 1. Students enter one at a time, and each picks the empty seat that **maximizes the distance to the closest occupied seat**. If several seats achieve that maximum distance, the student takes the **lowest-numbered** one. If the room is empty, the student sits in seat 0. - ExamRoom(n) creates an empty room. - seat() seats a new student using the rule above and returns the seat number. - leave(p) makes the student in seat p leave. Seat p is guaranteed to be occupied. seat is only called when at least one seat is empty. The room can be huge, so avoid work proportional to n per call.

Examples

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"] [[8],[],[],[],[],[3],[]]
Output: [null,0,7,3,5,null,2]
The second student goes to the far end (7). Between 0 and 7, seats 3 and 4 both give distance 3, so 3 wins. Next, seat 5 gives distance 2. After seat 3 empties, the best distance is 2, reached by seats 2 and 3; seat 2 is lower.
Input: ["ExamRoom","seat","leave","seat"] [[1],[],[0],[]]
Output: [null,0,null,0]
A one-seat room always uses seat 0.

Constraints

  • `1 <= n <= 10^9`
  • `leave(p)` is only called for an occupied seat `p`.
  • `seat` is only called when the room has an empty seat.
  • At most 10^4 calls in total.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More design problems