Checkout Server Rotation
An online shop runs its checkout service on a few identical servers behind a load balancer. Most requests take a few milliseconds, but a checkout that waits on a card payment can hold its connection for seconds. Health checks mark servers down and up again, and a server that goes down still has to finish the checkouts it already holds.
The balancer can hand out requests in turn (round robin) or send each one to the server with the fewest open connections (least connections). These are the two strategies from Load Balancing; you build both behind one switch so you can compare them.
Your task
Write a class Balancer:
constructor(servers, strategy):serverslists distinct server names in a fixed order; all start up, with 0 open connections.strategyis"round-robin"or"least-connections".route(): pick a server that is up, add one open connection to it, and return its name. If every server is down, returnnull(Nonein Python) and change nothing.finish(server): one connection on that server closes. Ignore it if the server has 0 open connections.setHealth(server, up): mark the server up (true) or down (false). Its open connections stay open either way.open(server): return the server's number of open connections.
Round robin keeps a cursor that starts at position 0. route looks at the server at the cursor, then the next ones, wrapping around the end of the list, and picks the first that is up. The cursor then moves to the position just after the picked server.
Least connections picks the up server with the fewest open connections; on a tie, the one that comes first in servers.
class Balancer
Examples
new Balancer(["s1", "s2", "s3"], "round-robin")
.route()
.route()
.setHealth("s2", false)
.route()
.route()
.route()
.open("s3")[null, "s1", "s2", null, "s3", "s1", "s3", 2]
Round robin hands out s1, then s2. Then s2 is marked down. The cursor is on s3, so s3 is next, and the cursor wraps to s1. After s1 the cursor is on s2, which is down, so the balancer skips to s3. s3 now has 2 open connections because nothing has finished.
new Balancer(["s1", "s2", "s3"], "least-connections")
.route()
.route()
.route()
.finish("s2")
.route()
.route()
.setHealth("s2", false)
.route()[null, "s1", "s2", "s3", null, "s2", "s1", null, "s3"]
All start at 0, so ties go to the first: s1, then s2, then s3, one connection each. s2 finishes a request and drops to 0, so it gets the next one. Now all three have 1, and the tie goes to s1, which reaches 2. Then s2 is marked down. Of the servers still up, s3 has 1 open connection and s1 has 2, so s3 gets the request.
Constraints
- 1 ≤ servers.length ≤ 50
- Server names are distinct, non-empty strings; finish, setHealth and open always name a server from the list.
- At most 2,000 calls per test
Start with brute force
A first version of round robin often keeps a counter, starts at servers[counter % n], steps forward with a while loop until it finds a server that is up, and then adds 1 to the counter. It loops forever when every server is down. It also gives the server after a dead one a double share: with a, b, c and b down, counter 1 lands on b and moves on to c, then counter 2 lands on c again.
Scanning forward from a cursor that sits just after the last pick fixes both: the scan is bounded by n, and the turn passes on in order. With at most 50 servers, an O(n) scan per request is fine; a balancer with thousands of backends would keep a heap or buckets of connection counts for least connections.
Hints
0 of 4 shown- Hint 1
Both strategies share most of their state. What does the balancer need to know about each server, whatever the strategy?
- Hint 2
Per server: whether it is up and how many connections are open. Keep the names in a list for order, and a map from name to position so
finish,setHealthandopenare one lookup each. - Hint 3
For round robin, the cursor is a position in the list. Try at most
npositions starting at the cursor, using(cursor + i) % n. If none is up, return null without moving the cursor. - Hint 4
For least connections, scan every server, skip the ones that are down, and keep the first with the smallest count. A strict "less than" comparison gives the tie to the earlier server for free.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Keep three arrays indexed by position: names, up or down, and open connections. A map from name to position serves finish, setHealth and open. The two strategies differ only in how pick chooses a position.
Trace the second example (least connections):
- Counts [0, 0, 0]. Three routes give s1, s2, s3, each time the earliest of the smallest. Counts [1, 1, 1].
finish("s2"): counts [1, 0, 1]. The next route picks s2, the only server with 0. Counts [1, 1, 1].- All equal again, so s1 wins the tie. Counts [2, 1, 1].
- s2 goes down. Only s1 (2) and s3 (1) are candidates, so s3 gets it. Counts [2, 1, 2]: s2 still holds its connection until it finishes.
For round robin, the cursor sits just after the last pick, so the scan in the first example goes s1, s2, s3 (s2 is down by then), s1, then skips s2 and lands on s3. Moving the cursor past the picked server, not past the dead one, is what stops the server after a dead one from getting a double share.
In an interview, the choice is the point: round robin when requests cost about the same, least connections when some requests hold a server far longer, like these card payments.
class Balancer {
constructor(servers, strategy) {
this.names = servers;
this.index = new Map(servers.map((s, i) => [s, i]));
this.up = servers.map(() => true);
this.conns = servers.map(() => 0);
this.roundRobin = strategy === 'round-robin';
this.cursor = 0;
}
pick() {
const n = this.names.length;
if (this.roundRobin) {
for (let k = 0; k < n; k++) { // at most one lap
const i = (this.cursor + k) % n;
if (this.up[i]) { this.cursor = (i + 1) % n; return i; }
}
return -1;
}
let best = -1;
for (let i = 0; i < n; i++) { // strict < keeps the earliest on ties
if (this.up[i] && (best === -1 || this.conns[i] < this.conns[best])) best = i;
}
return best;
}
route() {
const i = this.pick();
if (i === -1) return null; // everything is down
this.conns[i]++;
return this.names[i];
}
finish(server) {
const i = this.index.get(server);
if (this.conns[i] > 0) this.conns[i]--;
}
setHealth(server, up) {
this.up[this.index.get(server)] = up; // open connections stay
}
open(server) {
return this.conns[this.index.get(server)];
}
}class Balancer:
def __init__(self, servers, strategy):
self.names = servers
self.index = {s: i for i, s in enumerate(servers)}
self.up = [True] * len(servers)
self.conns = [0] * len(servers)
self.round_robin = strategy == "round-robin"
self.cursor = 0
def _pick(self):
n = len(self.names)
if self.round_robin:
for k in range(n): # at most one lap
i = (self.cursor + k) % n
if self.up[i]:
self.cursor = (i + 1) % n
return i
return -1
best = -1
for i in range(n): # strict < keeps the earliest on ties
if self.up[i] and (best == -1 or self.conns[i] < self.conns[best]):
best = i
return best
def route(self):
i = self._pick()
if i == -1: # everything is down
return None
self.conns[i] += 1
return self.names[i]
def finish(self, server):
i = self.index[server]
if self.conns[i] > 0:
self.conns[i] -= 1
def set_health(self, server, up):
self.up[self.index[server]] = up # open connections stay
def open(self, server):
return self.conns[self.index[server]]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.