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.