Restaurant waitlist that seats the best-fitting party

Build the waitlist for a restaurant. Parties join with their size, and may leave before they are seated. When a table frees up, seat the party that should get it: the party that has waited longest among those that fit at the table. Keep each operation fast and explain your data structures.

Interface

Unless you agree on a different interface with the interviewer, assume:

• join(party_id: str, size: int) -> bool — adds the party to the end of the list. False if the id is already waiting.
• leave(party_id: str) -> bool — removes a waiting party. False if it is not waiting.
• seat(table_size: int) -> str | None — removes and returns the longest-waiting party with size <= table_size, or None if no party fits.

Example

join("kim", 4)     ->  True
join("lee", 2)     ->  True
join("ortiz", 6)   ->  True
join("pat", 2)     ->  True
seat(3)            ->  "lee"      # kim waited longer but does not fit
leave("pat")       ->  True
seat(2)            ->  None       # nobody of size 2 or less is left
seat(8)            ->  "kim"
seat(8)            ->  "ortiz"

Constraints

• Party sizes are 1 to S, with S small (say 20). Up to 10^5 operations.

Clarifying questions

• Which party should get a table: the longest-waiting one that fits, or the one that best fills the table?
• Is a large table wasted on a small party acceptable, or should it wait for a better fit?
• Can parties change size while waiting?
• Do we need to tell each party its position or expected wait?

What a strong answer covers

• One queue per party size, each in join order, plus a map from party id to its node: join and leave in O(1) with a linked hash map or doubly linked list per size.
• seat: look at the head of every queue with size <= table_size and take the one that joined first, using a global join counter. O(S) per call, which is effectively constant.
• The simpler single list with a scan (O(n) per seat) and when it is good enough.
• The alternative of a balanced tree keyed by join time with a size filter, and why per-size queues fit better when sizes are few.
• Tests: no party fits, leave of the head of a queue, rejoin after leaving, several parties of the same size.

Follow-ups

• Show each party its position and an estimated wait.
• Reservations at set times that take priority over the walk-in list.
• Prefer the best fit (smallest party that leaves the fewest empty seats), with the longest wait as a tie-break.