Dsa
Queue
Hard
The Fair-Share Multi-Channel Scheduler
You are building a task scheduler for multiple users. Each user has their own FIFO queue of tasks. To ensure fairness, the scheduler uses a 'User-Level Round Robin' strategy:
1. Maintain a queue of *active users* (users who have at least one task pending).
2. In each step, pick the user at the front of the active user queue.
3. Process exactly one task from that user's FIFO queue.
4. If that user still has tasks left, move the user to the back of the active user queue. Otherwise, remove them from the active user queue.
5. New tasks can arrive at any time. If a task arrives for a user not currently in the active user queue, that user is added to the *back* of the active user queue.
Input: N (number of tasks). Each task is `Timestamp UserID TaskID`. Tasks are sorted by Timestamp.
Output: The sequence of `TaskID` in the order they are processed.
Example:
Input:
4
0 Alice T1
0 Bob T2
0 Alice T3
5 Charlie T4
Output:
T1 T2 T3 T4
Key concepts
queueround-robinfair scheduling
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now