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
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.
Read the full Google Software Engineer interview experience this question came from
Simulate a restaurant **waitlist** by processing a sequence of operations and returning the result of each one.
Implement:
```python
def solution(operations):
...
```
`operations` is a list of tuples. Process them **in order** and return a list containing one result per operation (in the same order).
## Waitlist model
- Each party is identified by an integer **`partyId`**, assigned in increasing order starting from **1** — the first party added gets id `1`, the second gets `2`, and so on.
- Parties are kept in **arrival order** (FIFO): a party that joined earlier is considered to be *ahead of* a party that joined later.
- A party stays on the waitlist until it is either **seated** or **cancelled**.
## Operations
Each tuple's first element names the operation:
- **`('addParty', name, size)`** — Add a new party of the given `size` to the **end** of the waitlist. Return its newly assigned `partyId`.
- `name` is part of the input but has **no effect** on seating order or priority.
- **`('cancelParty', partyId)`** — If that party is still waiting, remove it from the waitlist and return **`True`**. If the party is not currently waiting (it was never added, already seated, or already cancelled), make no change and return **`False`**.
- **`('seatTable', capacity)`** — A table with the given `capacity` opens up. Seat the **earliest-arrived waiting party whose `size <= capacity`**, remove it from the waitlist, and return its `partyId`.
- The chosen party is the one with the smallest arrival time **among all fitting parties** — not necessarily the very front of the line. A later-arriving small party may be seated before an earlier-arriving party that is too large.
- If **no** waiting party fits (`size <= capacity`), return **`None`** and leave the waitlist unchanged.
- **`('getPosition', partyId)`** — Return how many parties are **currently ahead** of that party in waitlist order (i.e. the count of still-waiting parties that arrived before it). A party at the front of the line returns **`0`**. If the party is not currently waiting (never added, already seated, or cancelled), return **`-1`**.
## Output
Return the list of results, one entry per operation, in the order the operations were given. For an empty `operations` list, return an empty list.
## Example
```
operations = [('addParty', 'A', 4), ('addParty', 'B', 2),
('seatTable', 2), ('seatTable', 4)]
result = [1, 2, 2, 1]
```
`A` (id 1, size 4) and `B` (id 2, size 2) join. `seatTable(2)` can only fit `B`, so it seats party `2`. `seatTable(4)` then seats the remaining party `1`.
## 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.
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.
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.
Community answers
Answer by rupalsharmadel
#include
using namespace std;
class Fenwick {
int n;
vector tree;
public:
Fenwick(int n) : n(n), tree(n + 1, 0) {}
void update(int i, int delta) {
for (; i <= n; i += i & -i)
tree[i] += delta;
}
int query(int i) {
int s = 0;
for (; i > 0; i -= i & -i)
s += tree[i];
return s;
}
};
class Waitlist {
static const int MAXN = 200005;
Fenwick bit;
int nextId = 1;
int nextIndex = 1;
unordered_map> info;
vector< set > buckets;
public:
Waitlist() : bit(MAXN), buckets(21) {}
int addParty(string name, int size) {
int id = nextId++;
int idx = nextIndex++;
info[id] = {idx, size};
buckets[size].insert(idx);
bit.update(idx, 1);
return id;
}
bool cancelParty(int partyId) {
if (!info.count(partyId)) return false;
auto [idx, size] = info[partyId];
buckets[size].erase(idx);
bit.update(idx, -1);
info.erase(partyId);
return true;
}
int seatTable(int capacity) {
int bestIdx = INT_MAX;
int bestSize = -1;
for (int s = 1; s <= capacity; s++) {
if (!buckets[s].empty()) {
int idx = *buckets[s].begin();
if (idx < bestIdx) {
bestIdx = idx;
bestSize = s;
}
}
}
if (bestIdx == INT_MAX)
return -1;
int partyId = -1;
for (auto &p : info) {
if (p.second.first == bestIdx) {
partyId = p.first;
break;
}
}
buckets[bestSize].erase(bestIdx);
bit.update(bestIdx, -1);
info.erase(partyId);
return partyId;
}
int getPosition(int partyId) {
if (!info.count(partyId))
return -1;
int idx = info[partyId].first;
return bit.query(idx) - 1;
}
};