A copy shop has one big printer. With a plain FIFO queue, a customer who drops off 500 flyers blocks everyone behind them, so the shop serves customers in turns: each turn prints one job for one customer, then moves on to the next customer who's waiting.
Build FairQueue with:
submit(customer, job_id) -> None: add a job to the back of that customer's own queue. If the customer had no pending jobs, they join the back of the rotation.next_job() -> tuple[str, str] | None: take the customer at the front of the rotation, remove their oldest pending job and return(customer, job_id). If that customer still has pending jobs, they go to the back of the rotation; otherwise they leave it. ReturnNonewhen nothing is pending.pending(customer) -> int: how many jobs that customer has waiting (0for someone unknown).
Job ids are unique strings.
q = FairQueue()
q.submit("ann", "a1"); q.submit("ann", "a2"); q.submit("ann", "a3")
q.submit("bo", "b1")
q.next_job() # ("ann", "a1")
q.submit("cy", "c1") # cy joins the rotation behind bo and ann
q.next_job() # ("bo", "b1") bo is done and leaves the rotation
q.next_job() # ("ann", "a2")
q.submit("bo", "b2") # bo had nothing pending: back of the rotation, behind cy
q.next_job() # ("cy", "c1")
q.next_job() # ("ann", "a3")
q.next_job() # ("bo", "b2")
q.next_job() # None
Busy days have thousands of customers and hundreds of thousands of jobs, so both submit and next_job must be O(1): don't search a list of customers, and don't pop(0) from Python lists.
Show hint
keep a dict customer -> deque of job ids and one deque of customers for the rotation. A customer is in the rotation exactly when their deque is non-empty, so submit appends them to the rotation when their deque was empty.