Corporate Flight Bookings

Corporate Flight Bookings

What is this problem about?

In the Corporate Flight Bookings coding problem, you are given a set of bookings for n flights. Each booking is represented as [first, last, seats], meaning seats number of seats were booked for every flight from index first to last (inclusive). You need to return an array of size n containing the total number of seats booked for each flight.

Why is this asked in interviews?

Google and Amazon ask the Corporate Flight Bookings interview question to see if you can optimize a range-update problem. A naive approach would be to iterate through the range for every booking, which takes O(Bookings * n) time. The optimal solution uses a "Difference Array," reducing the complexity to O(Bookings + n). It evaluates your ability to use prefix sums for interval management.

Algorithmic pattern used

The primary Array interview pattern here is the Difference Array / Prefix Sum.

1. Create an array of size n + 1.
2. For each booking [i, j, k]:
   • Add k to arr[i-1].
   • Subtract k from arr[j] (if j < n).
3. Traverse the array once, calculating the running prefix sum. The prefix sum at any index p will correctly represent the total seats for flight p+1 because the "+k" starts the contribution and the "-k" ends it.

Example explanation

Flights: 5, Bookings: [[1, 2, 10], [2, 3, 20]]

1. Initial array: [0, 0, 0, 0, 0]
2. Booking 1 (1 to 2, 10 seats):
   • arr[0] += 10, arr[2] -= 10. Array: [10, 0, -10, 0, 0]
3. Booking 2 (2 to 3, 20 seats):
   • arr[1] += 20, arr[3] -= 20. Array: [10, 20, -10, -20, 0]
4. Calculate Prefix Sums:
   • 10
   • 10 + 20 = 30
   • 30 - 10 = 20
   • 20 - 20 = 0
   • 0 + 0 = 0 Result: [10, 30, 20, 0, 0].

Common mistakes candidates make

• Brute Force: Using nested loops for range updates, which will lead to a Time Limit Exceeded (TLE) error for large inputs.
• Index Off-by-one: Forgetting that flight indices are 1-based but the array is 0-based.
• Boundary Conditions: Not correctly subtracting the seats after the last flight in the booking range.

Interview preparation tip

Difference arrays are a "must-know" for range update problems. They turn a O(N) range update into an O(1) operation. Practice this alongside the "Sweep Line" algorithm, as they share similar concepts.