Design a waitlist manager
Company: Google
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: easy
Interview Round: Onsite
## Object-Oriented Design: Waitlist Manager
Design a **waitlist management component** (e.g., for a restaurant or event) that maintains **FIFO order** for parties as they join a waitlist.
### Requirements
Implement a class (or set of classes) with APIs similar to:
- `add(partyId, partySize, metadata) -> void`: Add a party to the end of the waitlist.
- `cancel(partyId) -> bool`: Remove a party if they are currently waiting.
- `nextParty() -> Party | null`: Return (and remove) the next eligible party to be seated.
- `peekNext() -> Party | null`: Return the next party without removing.
- `position(partyId) -> int | null`: Return the party’s current position (optional follow-up).
### Constraints / Expectations
- Aim for **efficient operations** (discuss time/space complexity).
- Assume `partyId` is unique.
- Handle edge cases (duplicate adds, canceling a non-existent party, empty waitlist).
### Follow-ups
- How would you support skipping parties temporarily (e.g., they don’t respond) and re-adding them later?
- How would your complexity change if you must support `position(partyId)` efficiently?
Quick Answer: This question evaluates object-oriented design and data-structure competency—modeling a FIFO waitlist API, managing unique party identifiers and edge cases, and reasoning about time and space complexity; it falls under the Software Engineering Fundamentals domain with emphasis on OOP and algorithms.