Seat Reservation Manager

MediumHeapheap

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

A venue has n seats numbered 1 to n, all initially free. Implement SeatManager: - SeatManager(n) creates the manager with n free seats. - reserve() books the **smallest-numbered** free seat and returns its number. - unreserve(seatNumber) makes the given seat free again. reserve is only called when at least one seat is free, and unreserve is only called on a seat that is currently reserved. Each operation should run in O(log n) time or better.

Examples

Input: ["SeatManager","reserve","reserve","unreserve","reserve","reserve","reserve"] [[4],[],[],[1],[],[],[]]
Output: [null,1,2,null,1,3,4]
Seats 1 and 2 are taken, then seat 1 is freed. The next reservation reuses 1 because it is the smallest free seat, followed by 3 and 4.
Input: ["SeatManager","reserve","reserve","reserve","unreserve","unreserve","reserve","reserve"] [[3],[],[],[],[3],[1],[],[]]
Output: [null,1,2,3,null,null,1,3]
With seats 1 and 3 freed, reservations hand them out smallest first: 1, then 3.

Constraints

  • 1 <= n <= 10^5
  • 1 <= seatNumber <= n
  • At most 10^5 calls are made in total.
  • `reserve` is called only when a seat is free; `unreserve` only on a reserved seat.

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 heap problems