Compute buffet revenue with capacity and waiting
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A casino buffet has a maximum capacity `capacity` (number of customers that can be seated at once).
You are given:
1) `prices`: an array where `prices[i]` is how much customer `i` is willing to pay.
2) `events`: an array of customer IDs. For each customer `id`, the 1st time `id` appears means the customer arrives; the 2nd time means the customer leaves; the 3rd time arrives again; the 4th time leaves again; etc. (Arrivals and departures are interleaved across customers.)
Rules:
- If a customer arrives and there is free capacity, they are seated immediately.
- If there is no free capacity, they wait in a FIFO queue.
- When a seated customer leaves, newly freed seats are immediately offered to waiting customers in FIFO order.
- If a waiting customer leaves before being seated, they simply leave the queue.
- Each customer pays **at most once total** (the first time they get seated). Subsequent visits, even if seated again, do not add revenue.
Return the total buffet revenue.
Example event interpretation:
- `events = [0, 1, 2, 0, 2]` means: 0 arrives → 1 arrives → 2 arrives → 0 leaves → 2 leaves.
Implement a function:
- Input: `int capacity, int[] prices, int[] events`
- Output: `long totalRevenue`
Quick Answer: This question evaluates event-driven simulation and state-management skills, including handling customer lifecycle, capacity constraints, FIFO queuing behavior, and revenue aggregation.
A casino buffet can seat at most `capacity` customers at the same time.
You are given:
- `prices`, where `prices[i]` is how much customer `i` is willing to pay.
- `events`, a chronological list of customer IDs.
For each customer ID, the 1st time it appears means the customer arrives, the 2nd time means they leave, the 3rd time means they arrive again, the 4th time means they leave again, and so on.
Rules:
- If a customer arrives and there is free capacity, they are seated immediately.
- If there is no free capacity, they wait in a FIFO queue.
- When a seated customer leaves, the newly freed seat is immediately offered to the earliest waiting customer.
- If a waiting customer leaves before being seated, they are removed from the queue.
- Each customer pays at most once total: only the first time they ever get seated. Any later seatings do not add more revenue.
Return the total buffet revenue.
Customer IDs are 0-based indices into `prices`.
Constraints
- 0 <= capacity <= 200000
- 0 <= n = len(prices) <= 200000
- 0 <= m = len(events) <= 200000
- 0 <= prices[i] <= 10^9
- 0 <= events[j] < n
- For each customer, appearances in `events` alternate arrival, leave, arrival, leave, ... starting with arrival