Design a waitlist system with top/bottom K
Company: Google
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
## Object-Oriented Design: Waitlist System
Design and implement (at the class/interface level) a **waitlist system** that supports the following operations:
### Core requirements
1. **Join the waitlist**: add a user/customer to the end of the waitlist.
2. **Leave the waitlist**: remove a specific user/customer from the waitlist.
3. **View the queue**: return the current waitlist order.
4. **Get top K**: return the first `k` users in the waitlist.
5. **Get bottom K**: return the last `k` users in the waitlist.
### Clarifications / assumptions (you may choose reasonable defaults)
- Each user has a unique `userId`.
- If a user tries to join twice, define the expected behavior (e.g., no-op, move to end, or error).
- If `k` is larger than the queue size, return as many as possible.
- Aim for clean OOD and efficient time complexity for typical operations.
Provide the main classes, methods, and the data structures you would use, along with time/space complexity and key edge cases.
Quick Answer: This question evaluates object-oriented design, data structure selection, and algorithmic complexity reasoning for implementing a waitlist that supports join/leave operations and top-K/bottom-K queries.