1602. Round Robin Desk

Medium3.5 points estimatedDesignDoubly-Linked ListHash Table
RPby Rohit Parihar

Design a help desk that serves customers in rounds. RoundRobinDesk() starts empty and keeps customer ids in a circular order with a pointer to the customer who is served next.

  • boolean add(int id) returns false if id is already present. Otherwise it places id directly before the pointer in the circle (so it is the last to be reached in the current round), returns true, and if the desk was empty the pointer now sits on it.
  • boolean remove(int id) returns false if id is absent; otherwise it unlinks it and returns true. If it was under the pointer, the pointer moves to the next customer.
  • int serveNext() returns the id under the pointer and moves the pointer forward one step, or -1 when empty.

Every operation must run in O(1) using a circular doubly linked list plus a hash map.

Example 1

Input:
operations = ["RoundRobinDesk","add","add","add","serveNext","serveNext","add","serveNext","serveNext","serveNext"]arguments = [[],[5],[7],[9],[],[],[3],[],[],[]]
Output:
[null,true,true,true,5,7,true,9,5,7]
Explanation:

The ring is 5, 7, 9; serving gives 5 then 7, and the new id 3 lands just before the pointer at 9, so 9, 5, 7 are served next.

Example 2

Input:
operations = ["RoundRobinDesk","serveNext","remove","add","add","serveNext","serveNext","remove","remove","serveNext"]arguments = [[],[],[1],[4],[4],[],[],[4],[4],[]]
Output:
[null,-1,false,true,false,4,4,true,false,-1]
Explanation:

Operations on an empty desk give -1 and false; the duplicate add of 4 returns false.

Constraints

0 ≤ id ≤ 109; at most 2000 calls in total.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(1) per call
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.