Skip to content
Hello Python

Seat Reservation Manager

Interview ProblemInterviewMediumHeapPriority Queue

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement SeatManager(n) with reserve(), which returns and reserves the smallest available seat, and unreserve(seatNumber), which makes a reserved seat available again.

Starter code

class SeatManager:
    def __init__(self, n):
        pass
Test cases

reuse-smallest

{
  "operations": [
    "SeatManager",
    "reserve",
    "reserve",
    "unreserve",
    "reserve",
    "reserve"
  ],
  "arguments": [
    [
      5
    ],
    [],
    [],
    [
      1
    ],
    [],
    []
  ]
}

Expected: [null,1,2,null,1,3]

Wizard outline
  1. Step 1: Initialize SeatManager

    Replace the empty starter with the first real state owned by SeatManager. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

  2. Step 2: Assemble the primary transition

    Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

  3. Step 3: Pass the Wizard Stateful Seat Reuse case

    Complete the readable core algorithm for one representative Interview case. Returned seats must take priority over every larger never-issued seat.

  4. Step 4: Harden the Wizard Stateful Seat Returned Order boundary

    Repair the reviewed boundary and pass the complete submission contract. Heap push/pop preserves the smallest-available contract without repeatedly sorting returned state.

Footguns and prerequisites
  • After unreserve, that smaller seat must be chosen before the next never-used number.
  • python specific rapid fire
Reviewed references
Practice prerequisites
  • Update a Bounded Heap(opens in a new tab)

    Update a Bounded Heap isolates after each value, the heap contains the largest min(k, processed_count) values seen so far. That focused state discipline is required when implementing seat reservation manager as a complete Interview Problem.

Recommended approach and implementation

Track next_unused starting at one and a min-heap of returned seats. reserve pops returned first or increments next_unused; unreserve pushes onto the heap.

Why it works: All available seats are partitioned into returned seats below next_unused and the never-used suffix beginning at next_unused. The heap minimum or suffix start is therefore the globally smallest available seat.

class SeatManager:
    """
    Checkpoint 1: initialize the state owned by this Interview contract.
    Checkpoint 2: assemble the primary transition without hiding the boundary.
    """
    def __init__(self, n):
        self.next_unused = 1
        self.returned = []
    def reserve(self):
        import heapq
        if self.returned:
            return heapq.heappop(self.returned)
        seat = self.next_unused
        self.next_unused += 1
        return seat
    def unreserve(self, seatNumber):
        import heapq
        heapq.heappush(self.returned, seatNumber)