Design a restaurant waitlist system

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