Next in Line

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

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Foursquare

Problem

A server pool's dispatch layer is driven by a replayed command stream ops, where each entry is a list: ['add_server', id] registers a server, ['remove_server', id] deregisters one, and ['get_server'] sends the next request to a server and returns its id. Requests go to servers in the order they registered, wrapping from the last back to the first, and when a server is deregistered the rotation carries on over the survivors so that the server that was due next still serves next, with none skipped or served twice in a single pass. Return the ids produced by the ['get_server'] entries in the order those entries appear; add_server and remove_server add nothing to the output.

Every server gets its turn. Keep the line honest as the pool changes.

Example 1

Input:

ops = [["add_server","s1"],["add_server","s2"],["get_server"],["get_server"],["get_server"]]

Output:

["s1","s2","s1"]

Example 2

Input:

ops = [["add_server","a"],["add_server","b"],["add_server","c"],["get_server"],["get_server"],["remove_server","b"],["get_server"],["get_server"],["get_server"]]

Output:

["a","b","c","a","c"]

Worked solution and explanation

What this problem is really about

This is an identity-stable rotation dressed up as a load balancer. The skill being probed: can you keep a 'next server' pointer valid when the list it indexes into mutates underneath it? Anyone can return servers[i] and bump i. The whole problem lives in the removal: when a server leaves, every index after it shifts down by one, so a pointer that does not move with it either skips the server that was due next or serves someone twice. Get that wrong and your example trace silently disagrees with the expected output, which is exactly how candidates lose this one.

Two readings, only one is right

There are two natural ways to handle a removal, and they produce different answers on the very first test that removes a server. The phrase 'the server due next still serves next, none skipped or served twice' picks the second one.

Global step counter (wrong here)
Keep one counter and read servers[count % len] each call. Simple, but a removal shrinks len without preserving WHO was due next. On the three-server case it yields a, b, a, c, a: after removing b it jumps back to a, skipping the c that was on deck.
Identity-stable pointer (correct)
Track the index of the next server to serve, and when a removal happens at a position before that index, shift the pointer down by one so it keeps pointing at the SAME server. The three-server case yields a, b, c, a, c.

Building the solution

Step 1: Keep servers in an ordered list

A list of ids preserves registration order, which is the rotation order. add_server appends; remove_server drops the id. The list is the single source of truth for who is in the pool and in what order.

Step 2: Point at the next server, not a running total

Hold the index of the server to serve on the NEXT get_server. Each call returns servers[next_index] and advances with (next_index + 1) % len(servers) so it wraps cleanly off the end.

Step 3: Shift the pointer to absorb the removal

Find the leaving server's position, remove it, and if that position sits before next_index, decrement next_index by one so it still references the same server it did before. Then take it modulo the new length (or reset to 0 if the pool emptied) so it stays in range.

Step 4: Drive it from the ops stream

Walk ops, dispatch on the first element, and append ONLY get_server results to the output list. Registrations and deregistrations mutate state but contribute nothing to what you return.

Identity-stable round-robin
def load_balancer_demo(ops: list[list]) -> list:
    class LoadBalancer:
        def __init__(self):
            self.servers = []
            self.next_index = 0

        def add_server(self, server_id):
            self.servers.append(server_id)

        def remove_server(self, server_id):
            position = self.servers.index(server_id)
            self.servers.remove(server_id)
            if position < self.next_index:
                self.next_index -= 1
            if self.servers:
                self.next_index %= len(self.servers)
            else:
                self.next_index = 0

        def get_server(self):
            server = self.servers[self.next_index]
            self.next_index = (self.next_index + 1) % len(self.servers)
            return server

    balancer = LoadBalancer()
    dispatched = []
    for op in ops:
        action = op[0]
        if action == "add_server":
            balancer.add_server(op[1])
        elif action == "remove_server":
            balancer.remove_server(op[1])
        elif action == "get_server":
            dispatched.append(balancer.get_server())
    return dispatched

Common follow-up questions