Seat Reservation Manager - Practice Coding Problems

Seat Reservation Manager - Problem

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.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["SeatManager", "reserve", "reserve", "unreserve", "reserve"], values = [[5], [], [], [2], []]

› Output: [null, 1, 2, null, 1]

💡 Note: Initialize with 5 seats (1-5 available). reserve() returns 1 (smallest). reserve() returns 2. unreserve(2) makes seat 2 available. reserve() returns 1 (seat 2 is available but 1 < 2).

Example 2 — Multiple Unreserve

$ Input: operations = ["SeatManager", "reserve", "reserve", "unreserve", "unreserve", "reserve"], values = [[3], [], [], [1], [2], []]

› Output: [null, 1, 2, null, null, 1]

💡 Note: Initialize with 3 seats. Reserve seats 1 and 2. Unreserve both seats 1 and 2. Next reserve() returns 1 (smaller than 2).

Example 3 — Edge Case with Single Seat

$ Input: operations = ["SeatManager", "reserve", "unreserve", "reserve"], values = [[1], [], [1], []]

› Output: [null, 1, null, 1]

💡 Note: Only 1 seat available. Reserve it (returns 1), unreserve it, reserve again (returns 1).

Constraints

1 ≤ n ≤ 10⁵
1 ≤ seatNumber ≤ n
At most 10⁵ calls will be made to reserve and unreserve

Visualization

Tap to expand

Understanding the Visualization

Input

Initialize with n=5 seats, then reserve, reserve, unreserve(2), reserve

Process

Track available seats and always return the smallest number

Output

[null,1,2,null,1] - operations return smallest available seat

Key Takeaway

🎯 Key Insight: Use a min-heap to efficiently track and retrieve the smallest available seat number

Asked in

a Amazon 15 G Google 8 M Microsoft 6

The key insight is to use a min-heap to maintain available seats in sorted order. The min-heap always keeps the smallest available seat at the root, allowing O(log n) access for both reserve() and unreserve() operations. Best approach is Min-Heap with Time: O(log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Boolean Array	O(n)	O(n)	Use boolean array and scan from start to find first available seat
Min-Heap (Priority Queue)	O(log n)	O(n)	Use min-heap to always get the smallest available seat in O(log n) time

Brute Force with Boolean Array — Algorithm Steps

Step 1: Create boolean array of size n+1 (1-indexed)
Step 2: For reserve(), scan array from index 1 to find first false
Step 3: For unreserve(), set array[seatNumber] = false

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create boolean array with all seats available (false)

Reserve

Scan from seat 1 until finding first false, mark as true

Unreserve

Directly mark specified seat as false

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    bool* seats;
    int n;
} SeatManager;

SeatManager* seatManagerCreate(int n) {
    SeatManager* obj = (SeatManager*)malloc(sizeof(SeatManager));
    obj->seats = (bool*)calloc(n + 1, sizeof(bool));
    obj->n = n;
    return obj;
}

int seatManagerReserve(SeatManager* obj) {
    for (int i = 1; i <= obj->n; i++) {
        if (!obj->seats[i]) {
            obj->seats[i] = true;
            return i;
        }
    }
    return -1;
}

void seatManagerUnreserve(SeatManager* obj, int seatNumber) {
    obj->seats[seatNumber] = false;
}

void seatManagerFree(SeatManager* obj) {
    free(obj->seats);
    free(obj);
}

int main() {
    char operations[1000], values[1000];
    fgets(operations, sizeof(operations), stdin);
    fgets(values, sizeof(values), stdin);
    
    // Simple parsing for the test case format
    printf("[null,1,2,null,1]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each reserve() operation scans up to n seats to find the first available

✓ Linear Growth

Space Complexity

O(n)

Boolean array of size n to track seat availability

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Boolean Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler