# Next in Line > Every server gets its turn. Keep the line honest as the pool changes. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L4 ## 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. ## 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. > **Read the example before you code** > > The expected output for the three-server case is the tell. After serving `a` then `b`, the next due server is `c`. Removing `b` must NOT change that: the next call still returns `c`, then `a`, then `c`. Any solution that re-seeds the rotation after a removal returns `a` there instead, and fails. --- ### 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** ```python 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 ``` > **Interviewers watch for** > > The decrement is conditional on purpose. Removing a server BEFORE the pointer shifts the pointer's target left, so you compensate. Removing a server AT or AFTER the pointer leaves the next-due server's index untouched, so you must NOT decrement there, or you would rewind into a server you already served. > **Common pitfall** > > Reaching for a global counter and `count % len(servers)`. It passes the no-removal cases and feels clean, then quietly returns the wrong server the first time the pool shrinks. The bug is invisible until you trace a removal by hand, which is precisely the case the interviewer seeds. > **Performance** > > Time: `add_server` is O(1); `get_server` is O(1); `remove_server` is O(n) because both the lookup and the list delete scan the list. Replaying m ops costs O(m + total removal work). Space: O(n) for the pool plus O(g) for the collected results. For thousands of servers you would swap the list for a structure with O(1) removal, but at interview scale the list is the readable, correct choice. ## Common follow-up questions - How would you support weighted distribution so a bigger server takes more requests per cycle? _(Tests extending the rotation to weight servers by capacity.)_ - What breaks if add, remove, and get are called concurrently from many threads? _(Tests awareness of locks, atomicity, or lock-free structures.)_ - How would you make removal O(1) without losing the rotation order? _(Tests trading the O(n) removal for O(1) at the cost of order or memory.)_ - Why is plain rotation a poor fit for long-lived connections? _(Tests connection-aware strategies like least-connections.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/next_in_line) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.