The Traffic Director

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4
Asked in
Foursquare

Problem

A load balancer spreads incoming requests across a fixed pool of servers so the work stays evenly divided. Given the ordered servers pool and the requests in arrival order, assign each request to the next server in the rotation and return a dict mapping each request to the server it landed on.

Spread the load evenly - nobody should be doing all the work.

Example 1

Input:

servers = ["s1","s2","s3"], requests = ["r1","r2","r3","r4"]

Output:

{"r1":"s1","r2":"s2","r3":"s3","r4":"s1"}

Example 2

Input:

servers = ["a","b"], requests = ["x","y","z"]

Output:

{"x":"a","y":"b","z":"a"}

Worked solution and explanation

What this really is

This is load distribution wearing a server-pool costume. The real skill: cycling the assignment position through a fixed pool so it wraps back to the front instead of running off the end. Anyone can index servers[i] for the first few requests. The moment there are more requests than servers, a naive index throws IndexError. Fold the position back to the pool's start (modulo is the cleanest way to do it) and the rotation takes care of itself.

Break down the requirements

Step 1: Iterate requests with their index

Walk the requests in arrival order, keeping each one's position. That position is what decides which server it lands on.

Step 2: Wrap the position back to the pool start

The server index is i % len(servers). As i climbs past the pool size, the remainder cycles 0, 1, 2, 0, 1, 2 and the assignment wraps back to the front on its own. A raw servers[i] would blow up here; the wrap is the whole point.

Step 3: Build and return the assignment dict

Map each request to its server in a dict. If a request name repeats, the later write wins, which is the natural dict behavior here.

The solution

Cyclic assignment that wraps the position
def load_balancer_round_robin(servers: list, requests: list) -> dict:
    assignments = {}
    for i, request in enumerate(requests):
        assignments[request] = servers[i % len(servers)]
    return assignments

Common follow-up questions