Weighted round-robin task scheduler

Python data engineering interview problem. Difficulty: advanced. Pattern: Streaming. About 20 minutes. Part of the Pro drill bank.

A task scheduler should pick workers in weighted round-robin so a worker with twice the weight gets roughly twice the jobs.

A scheduler hands out jobs to workers in turns, but some workers should get more turns in a row than others. This is weighted round-robin. workers is a list of (name, weight) pairs. Go through the workers in order. Each worker gets weight turns in a row before the next worker starts. After the last worker, start again from the first. Return the list of the first steps names. If steps is 0 or less, or there are no workers, return []. Write weighted_round_robin(workers, steps). With [('a', 2), ('b', 1)] and 5 steps the result is ['a', 'a', 'b', 'a', 'a']: a gets 2 turns, b gets 1, then a starts again and the list stops after 5 names. The starter file already has the function name and its print lines. Keep them and fill in the body.

Requirements

• Give each worker weight turns in a row.
• Cycle through the workers in order.
• Stop after exactly steps names.
• Return [] for no workers or no steps.

Constraints

• workers is a list of (name, weight) pairs with positive whole weights.
• steps is a whole number.

Examples

Input: weighted_round_robin([('a', 2), ('b', 1)], 5) Output: ['a', 'a', 'b', 'a', 'a'] This input follows the stated rules and produces this output.

Topics: lakebench, python, queue.

More Python interview questions · All interview problems · Learn data engineering