Watch 3 video solutions for Flight Occupancy and Waitlist Analysis, a medium level problem involving Database. This walkthrough by Everyday Data Science has 578 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Flights
+-------------+------+
| Column Name | Type |
+-------------+------+
| flight_id | int |
| capacity | int |
+-------------+------+
flight_id is the column with unique values for this table.
Each row of this table contains flight id and its capacity.
Table: Passengers
+--------------+------+ | Column Name | Type | +--------------+------+ | passenger_id | int | | flight_id | int | +--------------+------+ passenger_id is the column with unique values for this table. Each row of this table contains passenger id and flight id.
Passengers book tickets for flights in advance. If a passenger books a ticket for a flight and there are still empty seats available on the flight, the passenger ticket will be confirmed. However, the passenger will be on a waitlist if the flight is already at full capacity.
Write a solution to report the number of passengers who successfully booked a flight (got a seat) and the number of passengers who are on the waitlist for each flight.
Return the result table ordered by flight_id in ascending order.
The result format is in the following example.
Example 1:
Input: Flights table: +-----------+----------+ | flight_id | capacity | +-----------+----------+ | 1 | 2 | | 2 | 2 | | 3 | 1 | +-----------+----------+ Passengers table: +--------------+-----------+ | passenger_id | flight_id | +--------------+-----------+ | 101 | 1 | | 102 | 1 | | 103 | 1 | | 104 | 2 | | 105 | 2 | | 106 | 3 | | 107 | 3 | +--------------+-----------+ Output: +-----------+------------+--------------+ | flight_id | booked_cnt | waitlist_cnt | +-----------+------------+--------------+ | 1 | 2 | 1 | | 2 | 2 | 0 | | 3 | 1 | 1 | +-----------+------------+--------------+ Explanation: - Flight 1 has a capacity of 2. As there are 3 passengers who have booked tickets, only 2 passengers can get a seat. Therefore, 2 passengers are successfully booked, and 1 passenger is on the waitlist. - Flight 2 has a capacity of 2. Since there are exactly 2 passengers who booked tickets, everyone can secure a seat. As a result, 2 passengers successfully booked their seats and there are no passengers on the waitlist. - Flight 3 has a capacity of 1. As there are 2 passengers who have booked tickets, only 1 passenger can get a seat. Therefore, 1 passenger is successfully booked, and 1 passenger is on the waitlist.
Problem Overview: Each flight has a fixed seat capacity. Passengers book seats over time, and bookings are processed in chronological order. If bookings exceed capacity, extra passengers go to the waitlist. The task is to compute how many passengers are confirmed and how many are waitlisted for every flight.
Approach 1: Correlated Subquery Simulation (O(n^2) time, O(1) space)
A straightforward SQL approach simulates the booking order for each passenger. For every booking row, count how many passengers booked the same flight earlier using a correlated subquery. If that count is less than or equal to the flight capacity, the passenger is confirmed; otherwise they are waitlisted. After assigning the status, aggregate counts per flight. This approach works but performs poorly because each row triggers another scan of the bookings table.
Approach 2: Window Function with ROW_NUMBER (O(n log n) time, O(n) space)
The efficient solution uses a SQL window function. Partition bookings by flight_id and order them by booking_time. Apply ROW_NUMBER() to assign the chronological booking position for every passenger within that flight. Join the result with the flight capacity table and compare the row number with the capacity. If row_number <= capacity, the passenger gets a confirmed seat; otherwise they fall into the waitlist. Finally, group by flight and count confirmed vs waitlisted passengers. Window functions avoid repeated scans and express the booking order directly in a single pass over the sorted dataset.
This approach relies on concepts from database querying and SQL window functions. The key insight is that the seat assignment is simply the booking order relative to capacity.
Recommended for interviews: The window function approach is what interviewers expect for SQL-focused problems. It shows you understand partitioning, ordering, and analytical functions like ROW_NUMBER(). Mentioning the correlated subquery method first demonstrates the baseline logic, while the window function solution shows practical SQL optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Correlated Subquery Simulation | O(n^2) | O(1) | Small datasets or when window functions are unavailable |
| Window Function with ROW_NUMBER | O(n log n) | O(n) | General case; best SQL solution for ordered seat allocation problems |