Design a Fair Event Registration Queue API
Design an in-memory service, following Object-Oriented Design (OOD) principles, to manage event registrations. The core requirement is fairness, which is defined as serving users strictly in the order they registered (First-In, First-Out - FIFO).
Users should be able to perform the following actions:
- Register for the event.
- Unregister (cancel) their registration.
- Query the first
kusers in the current fair registration order.
Define and implement the following API operations:
register(userId)unregister(userId)topK(k) -> List<userId>(returns the earliestkcurrently-registered users).
Your design should preserve the original registration order among active users and handle unregister operations efficiently. Discuss the time and space complexity of your solution, as well as key edge cases such as duplicate registrations or unregistering a non-existent user.
AI interview prep
Core dilemma
Maintaining strict FIFO order for registrations while efficiently handling cancellations (removals from the middle of the queue) without degrading performance.
3 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design a Fair Event Registration Queue API
Design an in-memory service, following Object-Oriented Design (OOD) principles, to manage event registrations. The core requirement is fairness, which is defined as serving users strictly in the order they registered (First-In, First-Out - FIFO).
Users should be able to perform the following actions:
- Register for the event.
- Unregister (cancel) their registration.
- Query the first
kusers in the current fair registration order.
Define and implement the following API operations:
register(userId)unregister(userId)topK(k) -> List<userId>(returns the earliestkcurrently-registered users).
Your design should preserve the original registration order among active users and handle unregister operations efficiently. Discuss the time and space complexity of your solution, as well as key edge cases such as duplicate registrations or unregistering a non-existent user.