Compute Buffet Revenue with Waiting Guests and Repeat Visits
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A buffet has a limited number of seats. Guests arrive, wait if necessary, eat if seated, and eventually leave. Each guest has a fixed amount they are willing to pay, but pays at most once during the entire day even if they visit more than once. Compute the day's total revenue.
### Function Contract
Implement `compute_day_gains(nb_seats, paying_guests, guest_movements) -> int`.
`paying_guests[g]` is the amount guest `g` pays on their first completed seated visit. Process `guest_movements` in order. Each occurrence of a guest identifier alternates between that guest arriving and departing: first arrival, then departure, then another arrival, and so on. Every arrival has a later matching departure, and a guest cannot have two active visits at once.
### Seating and Payment Rules
- The restaurant starts empty.
- An arrival takes a free seat immediately; otherwise the guest joins the waiting line.
- For this exercise, the line is FIFO. When a seated guest departs, the longest-waiting guest still in line immediately takes the freed seat before the next movement is processed.
- A departure by a waiting guest means that guest became bored and left without eating. It removes the guest from the line and does not free a seat.
- A guest who departs after being seated pays their stated amount if they have not paid on an earlier visit that day.
- A returning guest who already paid still requires a seat but never pays again.
### Constraints and Clarifications
- `1 <= len(paying_guests) <= 10`.
- `2 <= len(guest_movements) <= 26`.
- Every movement is a valid guest identifier.
- As explicit numeric practice bounds, `0 <= nb_seats <= 100` and each payment is an integer from `0` through `1000000`.
- All visits are closed by the end of the movement sequence.
- FIFO admission and immediate reuse of a freed seat make the waiting behavior deterministic.
### Examples
```text
nb_seats = 1
paying_guests = [10, 20, 30]
guest_movements = [0, 1, 2, 1, 0, 2]
Output: 40
```
Guest `1` leaves while waiting and pays nothing. Guest `0` pays 10 when leaving; guest `2` then takes the seat and later pays 30.
```text
nb_seats = 1
paying_guests = [5]
guest_movements = [0, 0, 0, 0]
Output: 5
```
The same guest completes two seated visits but pays only once.
```hint A visit state and a payment state are different
A guest can be outside, waiting, or seated during a visit. Whether that guest has already paid must survive across later visits.
```
Overview: Simulate buffet seating, FIFO waiting, early departures, and repeat visits while charging each guest at most once per day.
A buffet has `nb_seats` seats and starts the day empty. `paying_guests[g]` is the amount guest `g` pays on their first completed seated visit; a guest pays at most once during the entire day, even if they visit more than once.
Process `guest_movements` in order. Each occurrence of a guest identifier alternates between that guest arriving and that guest departing: the first occurrence of `g` is an arrival, the second is a departure, the third is another arrival, and so on. Every arrival has a later matching departure, and a guest cannot have two active visits at once.
Seating and payment rules:
- An arrival takes a free seat immediately; otherwise the guest joins the waiting line.
- The waiting line is FIFO. When a seated guest departs, the longest-waiting guest still in line immediately takes the freed seat, before the next movement is processed.
- A departure by a guest who is still waiting means that guest became bored and left without eating. It removes the guest from the line and does not free a seat.
- A guest who departs after being seated pays `paying_guests[g]` if they have not paid on an earlier visit that day.
- A returning guest who already paid still requires a seat but never pays again.
Return the total amount collected during the day.
The total can never exceed `10 * 1000000 = 10000000`, so it fits in a 32-bit integer; it is still returned as a 64-bit value (Java `long`, C++ `long long`).
Example 1:
```text
nb_seats = 1
paying_guests = [10, 20, 30]
guest_movements = [0, 1, 2, 1, 0, 2]
Output: 40
```
Guest `0` takes the only seat, and guests `1` and `2` wait in that order. Guest `1` departs while waiting, so it pays nothing and frees no seat. Guest `0` then departs and pays 10, guest `2` immediately takes the freed seat and later departs and pays 30, for a total of 40.
Example 2:
```text
nb_seats = 1
paying_guests = [5]
guest_movements = [0, 0, 0, 0]
Output: 5
```
The same guest completes two seated visits but pays only once, so the total is 5.
Constraints
- 0 <= nb_seats <= 100
- 1 <= len(paying_guests) <= 10
- Each payment is an integer from 0 through 1000000
- 2 <= len(guest_movements) <= 26
- Every movement is a valid guest identifier: 0 <= guest_movements[i] < len(paying_guests)
- Occurrences of a guest alternate arrival, departure, arrival, ...; a guest never has two active visits at once
- All visits are closed by the end of the movement sequence
- The returned total is at most 10 * 1000000 = 10000000
Examples
Input: (1, [7], [0, 0])
Expected Output: 7
Explanation: Minimum valid day: one guest takes the only seat and pays 7 on departure.
Input: (0, [10, 20], [0, 1, 1, 0])
Expected Output: 0
Explanation: With zero seats nobody is ever seated, so both departures are bored departures and nothing is paid.
Hints
- Each occurrence of a guest identifier flips that guest's visit state, so decide what a movement means from that guest's current state rather than from its position in the list.
- A guest's visit state (outside, waiting, seated) is a different thing from whether that guest has already paid today; the payment fact has to survive across later visits.
- A seat that opens up never stays open while someone is still in line - settle that handoff before you read the next movement.