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 Google.

What role is this question designed for?

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

Design a restaurant waitlist system | Google Coding Question

Quick Overview

This question evaluates a candidate's ability to design efficient data structures and algorithms for managing an ordered waitlist with dynamic additions, cancellations, and capacity-based selections, emphasizing performance under high operation counts.

Design a restaurant waitlist system

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are implementing the waitlist system for a restaurant. Parties arrive over time, can cancel, and get seated when a table becomes available. ## Rules - Each party has a unique `partyId`, a `name`, and a `size` (number of people). - Parties are seated in **arrival order**, but only if they **fit** the available table. - When a table of capacity `c` becomes available, you must seat the **earliest-arrived** party whose `size <= c`. - If no party fits, the table remains unused for that event. ## Operations to support Design a data structure / class that supports the following operations efficiently: 1. `addParty(name, size) -> partyId` - Adds a new party to the end of the waitlist and returns its id. 2. `cancelParty(partyId) -> bool` - Removes the party from the waitlist if present. - Returns `true` if removed, otherwise `false`. 3. `seatTable(capacity) -> partyId or null` - Finds and removes the earliest party with `size <= capacity`. - Returns that party’s id, or `null` if nobody fits. 4. `getPosition(partyId) -> int` - Returns how many parties are ahead of this party in the current waitlist order (0-based). - If the party is not in the waitlist, return `-1`. ## Constraints - Up to `2 * 10^5` operations. - Party size is a small positive integer (e.g., 1–20). - Aim for better-than-linear time per operation (especially for `seatTable` and `getPosition`). ## Example (one possible interaction) - addParty("A", 4) -> id1 - addParty("B", 2) -> id2 - seatTable(2) -> id2 (B fits and is earliest among those that fit) - seatTable(4) -> id1

Quick Answer: This question evaluates a candidate's ability to design efficient data structures and algorithms for managing an ordered waitlist with dynamic additions, cancellations, and capacity-based selections, emphasizing performance under high operation counts.

Process a sequence of restaurant waitlist operations efficiently. Each new party gets the next integer partyId starting from 1. Parties remain ordered by arrival time, but when a table becomes available, you must seat the earliest-arrived party whose size is less than or equal to the table capacity. If no waiting party fits, that seating event returns None and the waitlist does not change. Implement a function that receives all operations and returns the result of every operation in order. Supported operations: - ('addParty', name, size): add a party to the end of the waitlist and return its partyId. - ('cancelParty', partyId): remove that party if it is still waiting; return True if removed, otherwise False. - ('seatTable', capacity): seat and remove the earliest waiting party with size <= capacity; return its partyId, or None if nobody fits. - ('getPosition', partyId): return how many parties are currently ahead of that party in waitlist order, or -1 if the party is not waiting. The name is part of the input format but does not affect seating priority.

Constraints

0 <= len(operations) <= 2 * 10^5
For ('addParty', name, size), 1 <= size <= 20
For ('seatTable', capacity), 1 <= capacity <= 20
partyId values are assigned in increasing order starting from 1
Aim for better-than-linear time per operation

Examples

Input: [('addParty', 'A', 4), ('addParty', 'B', 2), ('seatTable', 2), ('seatTable', 4)]

Expected Output: [1, 2, 2, 1]

Explanation: Party ids start at 1. B is seated first because A does not fit a table of capacity 2, then A is seated by the next table.

Input: [('addParty', 'A', 4), ('addParty', 'B', 2), ('addParty', 'C', 3), ('getPosition', 3), ('seatTable', 2), ('getPosition', 3), ('cancelParty', 1), ('getPosition', 3), ('cancelParty', 1), ('seatTable', 2), ('seatTable', 3), ('getPosition', 3)]

Expected Output: [1, 2, 3, 2, 2, 1, True, 0, False, None, 3, -1]

Explanation: C starts with two parties ahead. B is seated first by the 2-seat table, then A cancels, leaving C at position 0. A second cancel on A fails, a 2-seat table fits nobody, then a 3-seat table seats C.

Input: [('addParty', 'A', 4), ('addParty', 'B', 5), ('addParty', 'C', 2), ('seatTable', 3), ('getPosition', 2), ('seatTable', 4), ('seatTable', 4), ('cancelParty', 2), ('seatTable', 5)]

Expected Output: [1, 2, 3, 3, 1, 1, None, True, None]

Explanation: For capacity 3, C is the earliest party that fits. Then B has one party ahead. A is later seated by a 4-seat table, another 4-seat table fits nobody, B cancels, and the final 5-seat table finds no one waiting.

Input: []

Expected Output: []

Explanation: No operations means no returned results.

Input: [('addParty', 'Solo', 1), ('getPosition', 1), ('seatTable', 1), ('getPosition', 1), ('cancelParty', 1)]

Expected Output: [1, 0, 1, -1, False]

Explanation: The only party starts at position 0, gets seated, is no longer on the waitlist, and therefore cannot be cancelled afterward.

Hints

Because party size is only 1..20, you can keep separate candidate structures for each size and check only a constant number of buckets when seating a table.
To answer getPosition after many cancellations and seatings, maintain active parties by arrival index in a Fenwick tree (Binary Indexed Tree) or another order-statistics structure.

Quick Overview