8. Fair Round-Robin Scheduling for Multiplexed Call Sessions

Problem

One outbound connection can be shared by several concurrent calls at once, each with its own queue of audio chunks waiting to be sent. If one call's queue is always drained first, its neighbors starve.

A round-robin scheduler fixes this by cycling through sessions and sending at most one chunk per session per pass, so every active call keeps making progress. Given each session's pending chunk queue, compute the overall send order.

Source: src/8_session_round_robin_scheduler.py

def round_robin_schedule(sessions: dict[str, list[str]]) -> list[str]:
    ...

Examples:
>>> round_robin_schedule({"A": ["a1", "a2"], "B": ["b1"]})
["a1", "b1", "a2"]

>>> round_robin_schedule({"X": ["x1", "x2"], "Y": ["y1", "y2"]})
["x1", "y1", "x2", "y2"]

Step-by-Step Approach

1. Load a rotation queue with every session id, in the order the input dict gives them, and give each session its own FIFO of pending chunks.
2. Repeatedly pop the session at the front of the rotation. If its queue is currently empty, drop it — it doesn't get a turn and doesn't return to the rotation.
3. If it has chunks, pop exactly one chunk from the front of that session's queue and append it to the output — this is the "at most one per pass" fairness rule.
4. After sending, check whether the session still has chunks left. If so, push its id back onto the end of the rotation queue so it gets another turn later; if its queue is now empty, let it drop out.
5. Continue until the rotation queue itself is empty, meaning every session has been fully drained (or started empty and was skipped immediately).
6. Return the accumulated output list, which interleaves chunks across sessions in round-robin order rather than draining any one session first.

The key insight is that the rotation queue itself acts as the scheduler's state — a session re-enters it only if it still has work, so sessions naturally drop out as they finish without any separate bookkeeping of who's "done."

Reference solution

from collections import deque


def round_robin_schedule(sessions: dict[str, list[str]]) -> list[str]:
    order = deque(sessions.keys())  # fixed rotation order
    queues = {sid: deque(chunks) for sid, chunks in sessions.items()}  # O(1) popleft per session
    output: list[str] = []
    while order:
        sid = order.popleft()
        q = queues[sid]
        if not q:
            continue  # already drained (or started empty); drop out of rotation
        output.append(q.popleft())
        if q:
            # still has work left: goes to the back of the line for its next turn
            order.append(sid)
    return output

Key Functions & Tricks

• collections.deque for both the rotation and each session's queue — O(1) popleft/append instead of O(n) list operations.
• Conditional re-enqueue — if q: order.append(sid) is what makes a session drop out of rotation exactly when (and only when) it's actually drained.
• while order as the loop's only termination condition — no separate "all done" flag needed, since an exhausted session simply never gets re-added.
• Per-session deque(chunks) copy — keeps the original input lists untouched while giving each session efficient pop-from-front semantics.

How to Recognize This Pattern