Scale Engineer

Seat Reservation Manager

Med
#1685Time: - **Constructor**: O(n) to initialize the boolean array. - **`reserve()`**: O(n) because in the worst case, we might have to scan the entire array to find an available seat. - **`unreserve()`**: O(1) for direct array access.Space: O(n) to store the state of `n` seats in the boolean array.2 companies
Patterns
Design
Data structures
Heap (Priority Queue)
Companies
DropboxSiemens

Prompt

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

  • SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
  • int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
  • void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

 

Example 1:

Input
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
Output
[null, 1, 2, null, 2, 3, 4, 5, null]

Explanation
SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats.
seatManager.reserve();    // All seats are available, so return the lowest numbered seat, which is 1.
seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5].
seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.reserve();    // The available seats are [3,4,5], so return the lowest of them, which is 3.
seatManager.reserve();    // The available seats are [4,5], so return the lowest of them, which is 4.
seatManager.reserve();    // The only available seat is seat 5, so return 5.
seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

 

Constraints:

  • 1 <= n <= 105
  • 1 <= seatNumber <= n
  • For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
  • For each call to unreserve, it is guaranteed that seatNumber will be reserved.
  • At most 105 calls in total will be made to reserve and unreserve.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a boolean array to keep track of the status of each seat. A true value at an index indicates the seat is reserved, while false indicates it's available.

Algorithm

  • SeatManager(n):
    • Create a boolean array reserved of size n+1.
  • reserve():
    • Iterate i from 1 to n.
    • If reserved[i] is false:
      • Set reserved[i] to true.
      • Return i.
  • unreserve(seatNumber):
    • Set reserved[seatNumber] to false.

Walkthrough

Initialization

In the SeatManager(n) constructor, we create a boolean array seats of size n + 1 (to accommodate 1-based indexing). We initialize all entries to false, signifying that all seats from 1 to n are initially available.

reserve()

To reserve the smallest-numbered seat, we perform a linear scan through the seats array, starting from index 1. The first index i we find where seats[i] is false corresponds to the smallest available seat. We then mark this seat as reserved by setting seats[i] = true and return the seat number i.

unreserve(seatNumber)

To unreserve a seat, we simply access the corresponding index in the array and set its value back to false. This is a constant-time operation.

class SeatManager {    private boolean[] reserved;    private int n;     public SeatManager(int n) {        this.n = n;        this.reserved = new boolean[n + 1]; // Using 1-based indexing    }     public int reserve() {        for (int i = 1; i <= n; i++) {            if (!reserved[i]) {                reserved[i] = true;                return i;            }        }        return -1; // Should not happen based on problem constraints    }     public void unreserve(int seatNumber) {        if (seatNumber >= 1 && seatNumber <= n) {            reserved[seatNumber] = false;        }    }}

Complexity

Time

- **Constructor**: O(n) to initialize the boolean array. - **`reserve()`**: O(n) because in the worst case, we might have to scan the entire array to find an available seat. - **`unreserve()`**: O(1) for direct array access.

Space

O(n) to store the state of `n` seats in the boolean array.

Trade-offs

Pros

  • Simple to understand and implement.

  • unreserve is very fast, taking O(1) time.

Cons

  • The reserve operation is slow, with a time complexity of O(n). This can lead to a 'Time Limit Exceeded' error on platforms with strict time limits, especially given that n can be up to 10^5.

Solutions

public class SeatManager { private SortedSet < int > availableSeats ; public SeatManager ( int n ) { availableSeats = new SortedSet < int >(); for ( int i = 1 ; i <= n ; i ++) { availableSeats . Add ( i ); } } public int Reserve () { int reservedSeat = availableSeats . Min ; availableSeats . Remove ( reservedSeat ); return reservedSeat ; } public void Unreserve ( int seatNumber ) { availableSeats . Add ( seatNumber ); } } /** * Your SeatManager object will be instantiated and called as such: * SeatManager obj = new SeatManager(n); * int param_1 = obj.Reserve(); * obj.Unreserve(seatNumber); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem