How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Upstart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Upstart during technical interviews.

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

Examples

Input: (2, [10, 20, 30], [0, 1, 2, 0, 2])

Expected Output: 60

Explanation: Customers 0 and 1 are seated first and pay 10 + 20. Customer 2 waits, then gets seated when customer 0 leaves and pays 30. Total revenue is 60.

Input: (1, [5, 7, 9], [0, 1, 1, 0])

Expected Output: 5

Explanation: Customer 0 is seated and pays 5. Customer 1 waits, then leaves before ever being seated, so they pay nothing.

Input: (1, [8], [0, 0, 0, 0])

Expected Output: 8

Explanation: Customer 0 visits twice. They pay only the first time they are seated, so the total stays 8.

Input: (2, [5, 10, 15, 20], [0, 1, 2, 3, 2, 0, 2, 1, 3, 2])

Expected Output: 50

Explanation: Customers 0 and 1 pay first. Customer 2 waits, customer 3 waits, then customer 2 leaves the queue. When 0 leaves, 3 is seated and pays. Later 2 arrives again, waits, and is seated when 1 leaves, paying then. Total is 5 + 10 + 20 + 15 = 50.

Input: (0, [4, 6], [0, 1, 0, 1])

Expected Output: 0

Explanation: There is no seating capacity, so everyone only waits and eventually leaves. No one is ever seated, so revenue is 0.

Input: (3, [2, 3], [])

Expected Output: 0

Explanation: No events means no arrivals and no revenue.

Hints

Track each customer's current state: absent, seated, or waiting.
A plain FIFO queue is not enough, because a waiting customer may leave before reaching the front. Use a data structure that preserves order and also supports fast removal by customer ID.

Quick Overview

This question evaluates event-driven simulation and state-management skills, including handling customer lifecycle, capacity constraints, FIFO queuing behavior, and revenue aggregation.