Simulate sticky load balancer with shutdown
Company: Stripe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Quick Answer: This question evaluates implementation skills for stateful simulation and algorithmic reasoning about load balancing, covering connection stickiness, capacity constraints, ordered re-routing on shutdown, and deterministic tie-breaking while testing data structure management and routing logic.
Part 1: Basic Load Balancing
Constraints
- 1 <= m <= 100000
- 0 <= len(requests) <= 200000
- Each request is a valid CONNECT request
- connectionId is a non-empty string
Examples
Input: (3, ['CONNECT a', 'CONNECT b', 'CONNECT c', 'CONNECT d', 'CONNECT e'])
Expected Output: ['a 0', 'b 1', 'c 2', 'd 0', 'e 1']
Explanation: Servers are chosen by minimum load, breaking ties by smaller index.
Input: (1, ['CONNECT x', 'CONNECT y'])
Expected Output: ['x 0', 'y 0']
Explanation: With one server, every connection goes to server 0.
Input: (2, [])
Expected Output: []
Explanation: Edge case: no requests means no log entries.
Input: (4, ['CONNECT p', 'CONNECT q', 'CONNECT r', 'CONNECT s'])
Expected Output: ['p 0', 'q 1', 'r 2', 's 3']
Explanation: The first four connections spread evenly across four servers.
Solution
def solution(m, requests):
import heapq
loads = [0] * m
heap = [(0, i) for i in range(m)]
heapq.heapify(heap)
log = []
for req in requests:
parts = req.split()
if not parts:
continue
cid = parts[1]
while heap:
load, server = heapq.heappop(heap)
if load == loads[server]:
break
else:
continue
log.append(f'{cid} {server}')
loads[server] += 1
heapq.heappush(heap, (loads[server], server))
return log
Time complexity: O(n log m), where n is the number of requests.. Space complexity: O(m).
Hints
- Keep track of each server's current load.
- A min-heap of (load, serverIndex) helps you find the next target server quickly.
Part 2: Load Balancer with Disconnect
Constraints
- 1 <= m <= 100000
- 0 <= len(requests) <= 200000
- Active connectionIds are unique at connect time
- If DISCONNECT references an inactive connection, ignore it
Examples
Input: (2, ['CONNECT a', 'CONNECT b', 'DISCONNECT a', 'CONNECT c'])
Expected Output: ['a 0', 'b 1', 'c 0']
Explanation: After 'a' disconnects, server 0 becomes the least loaded again.
Input: (3, ['CONNECT a', 'CONNECT b', 'CONNECT c', 'DISCONNECT b', 'CONNECT d'])
Expected Output: ['a 0', 'b 1', 'c 2', 'd 1']
Explanation: Disconnecting 'b' makes server 1 the best target for 'd'.
Input: (2, ['DISCONNECT ghost'])
Expected Output: []
Explanation: Edge case: disconnecting a missing connection does nothing.
Input: (1, ['CONNECT a', 'DISCONNECT a', 'CONNECT b'])
Expected Output: ['a 0', 'b 0']
Explanation: With one server, both successful connects route to server 0.
Solution
def solution(m, requests):
import heapq
loads = [0] * m
heap = [(0, i) for i in range(m)]
heapq.heapify(heap)
conn_to_server = {}
log = []
def get_server():
while heap:
load, server = heapq.heappop(heap)
if load == loads[server]:
return server
return None
for req in requests:
parts = req.split()
if not parts:
continue
if parts[0] == 'CONNECT':
cid = parts[1]
server = get_server()
if server is None:
continue
conn_to_server[cid] = server
log.append(f'{cid} {server}')
loads[server] += 1
heapq.heappush(heap, (loads[server], server))
else:
cid = parts[1]
if cid in conn_to_server:
server = conn_to_server.pop(cid)
loads[server] -= 1
heapq.heappush(heap, (loads[server], server))
return log
Time complexity: O(n log m), where n is the number of requests.. Space complexity: O(m + a), where a is the number of active connections..
Hints
- You need a map from connectionId to its current server.
- After a disconnect, the least-loaded server can change, so update your heap lazily.
Part 3: Sticky Load Balancer by Object
Constraints
- 1 <= m <= 100000
- 0 <= len(requests) <= 200000
- Active connectionIds are unique at connect time
- If all active connections for an objectId are gone, that object loses its sticky assignment
Examples
Input: (3, ['CONNECT c1 o1', 'CONNECT c2 o2', 'CONNECT c3 o1'])
Expected Output: ['c1 0', 'c2 1', 'c3 0']
Explanation: The third request sticks to server 0 because object o1 is already active there.
Input: (2, ['CONNECT a x', 'CONNECT b y', 'CONNECT c z', 'CONNECT d z', 'CONNECT e x', 'DISCONNECT a', 'DISCONNECT e', 'CONNECT f x'])
Expected Output: ['a 0', 'b 1', 'c 0', 'd 0', 'e 0', 'f 1']
Explanation: After both x-connections disconnect, object x loses stickiness and is routed again by load, this time to server 1.
Input: (1, ['DISCONNECT ghost', 'CONNECT p obj', 'CONNECT q obj'])
Expected Output: ['p 0', 'q 0']
Explanation: Edge case: the missing disconnect is ignored, and object stickiness keeps both connections on server 0.
Input: (2, [])
Expected Output: []
Explanation: Edge case: no requests.
Solution
def solution(m, requests):
import heapq
loads = [0] * m
heap = [(0, i) for i in range(m)]
heapq.heapify(heap)
conn = {}
obj_server = {}
obj_count = {}
log = []
def get_server():
while heap:
load, server = heapq.heappop(heap)
if load == loads[server]:
return server
return None
for req in requests:
parts = req.split()
if not parts:
continue
if parts[0] == 'CONNECT':
cid = parts[1]
oid = parts[2]
if oid in obj_server:
server = obj_server[oid]
else:
server = get_server()
if server is None:
continue
conn[cid] = (server, oid)
loads[server] += 1
heapq.heappush(heap, (loads[server], server))
log.append(f'{cid} {server}')
if oid not in obj_server:
obj_server[oid] = server
obj_count[oid] = 0
obj_count[oid] += 1
else:
cid = parts[1]
if cid in conn:
server, oid = conn.pop(cid)
loads[server] -= 1
heapq.heappush(heap, (loads[server], server))
obj_count[oid] -= 1
if obj_count[oid] == 0:
del obj_count[oid]
del obj_server[oid]
return log
Time complexity: O(n log m), where n is the number of requests.. Space complexity: O(m + a + o), where a is the number of active connections and o is the number of active objectIds..
Hints
- Track both connectionId -> (server, objectId) and objectId -> server.
- You also need a count of active connections per objectId so you know when to remove sticky state.
Part 4: Sticky Load Balancer with Capacity Limits
Constraints
- 1 <= len(capacity) <= 100000
- 0 <= capacity[i] <= 1000000000
- 0 <= len(requests) <= 200000
- If DISCONNECT references an inactive connection, ignore it
Examples
Input: ([1, 2], ['CONNECT a x', 'CONNECT b y', 'CONNECT c z', 'CONNECT d w'])
Expected Output: ['a 0', 'b 1', 'c 1']
Explanation: Server 0 fills first, then server 1 fills, so the last connect is rejected.
Input: ([1, 2], ['CONNECT a x', 'CONNECT b y', 'CONNECT c x'])
Expected Output: ['a 0', 'b 1']
Explanation: Object x is sticky to server 0, but server 0 is already full, so the third request is rejected.
Input: ([1, 1], ['CONNECT a x', 'CONNECT b y', 'DISCONNECT a', 'CONNECT c z'])
Expected Output: ['a 0', 'b 1', 'c 0']
Explanation: Disconnecting 'a' frees capacity on server 0.
Input: ([0, 2], ['CONNECT a x', 'CONNECT b x', 'CONNECT c y'])
Expected Output: ['a 1', 'b 1']
Explanation: Edge case: server 0 can never accept connections because its capacity is 0.
Solution
def solution(capacity, requests):
import heapq
m = len(capacity)
loads = [0] * m
heap = [(0, i) for i in range(m)]
heapq.heapify(heap)
conn = {}
obj_server = {}
obj_count = {}
log = []
def get_server():
while heap:
load, server = heapq.heappop(heap)
if load != loads[server]:
continue
if loads[server] >= capacity[server]:
continue
return server
return None
for req in requests:
parts = req.split()
if not parts:
continue
if parts[0] == 'CONNECT':
cid = parts[1]
oid = parts[2]
if oid in obj_server:
server = obj_server[oid]
if loads[server] >= capacity[server]:
continue
else:
server = get_server()
if server is None:
continue
conn[cid] = (server, oid)
loads[server] += 1
heapq.heappush(heap, (loads[server], server))
log.append(f'{cid} {server}')
if oid not in obj_server:
obj_server[oid] = server
obj_count[oid] = 0
obj_count[oid] += 1
else:
cid = parts[1]
if cid in conn:
server, oid = conn.pop(cid)
loads[server] -= 1
heapq.heappush(heap, (loads[server], server))
obj_count[oid] -= 1
if obj_count[oid] == 0:
del obj_count[oid]
del obj_server[oid]
return log
Time complexity: O(n log m), where n is the number of requests.. Space complexity: O(m + a + o), where a is the number of active connections and o is the number of active objectIds..
Hints
- A min-heap still works, but now you must skip servers whose load reached capacity.
- For sticky objects, do not search the heap first; check the required server directly.
Part 5: Sticky Load Balancer with Shutdown
Constraints
- 1 <= len(capacity) <= 100000
- 0 <= capacity[i] <= 1000000000
- 0 <= len(requests) <= 200000
- If DISCONNECT references an inactive connection, ignore it
- For deterministic shutdown behavior, evicted connections must be processed in their arrival order on that server
Examples
Input: ([2, 2, 2], ['CONNECT c1 o1', 'CONNECT c2 o2', 'CONNECT c3 o3', 'CONNECT c4 o4', 'SHUTDOWN 0'])
Expected Output: ['c1 0', 'c2 1', 'c3 2', 'c4 0', 'c1 1', 'c4 2']
Explanation: Server 0 is shut down, so c1 and c4 are evicted and re-routed in their original arrival order.
Input: ([3, 2, 2], ['CONNECT a x', 'CONNECT b y', 'CONNECT c x', 'SHUTDOWN 0'])
Expected Output: ['a 0', 'b 1', 'c 0', 'a 2', 'c 2']
Explanation: Both x-connections are evicted from server 0. After eviction, the first one chooses server 2, and the second sticks to it.
Input: ([3, 1, 2], ['CONNECT a x', 'CONNECT b y', 'CONNECT c x', 'CONNECT d x', 'SHUTDOWN 0'])
Expected Output: ['a 0', 'b 1', 'c 0', 'd 0', 'a 2', 'c 2']
Explanation: Only two of the three evicted x-connections can fit on server 2, so the last one is dropped. The processing order decides which IDs survive.
Input: ([1, 1], ['SHUTDOWN 1', 'DISCONNECT ghost', 'CONNECT a x', 'SHUTDOWN 0', 'CONNECT b y'])
Expected Output: ['a 0', 'a 1', 'b 0']
Explanation: Edge case: shutting down an empty server does nothing. Later, shutting down server 0 moves 'a' to server 1, and server 0 becomes available again.
Solution
def solution(capacity, requests):
import heapq
from collections import deque
m = len(capacity)
loads = [0] * m
heap = [(0, i) for i in range(m)]
heapq.heapify(heap)
conn = {} # connectionId -> (server, objectId, version)
obj_server = {}
obj_count = {}
server_queues = [deque() for _ in range(m)]
version = 0
log = []
def push_server(server):
heapq.heappush(heap, (loads[server], server))
def get_server(excluded=None):
while heap:
load, server = heapq.heappop(heap)
if load != loads[server]:
continue
if excluded is not None and server == excluded:
continue
if loads[server] >= capacity[server]:
continue
return server
return None
def place_connection(cid, oid, excluded=None):
nonlocal version
if oid in obj_server:
server = obj_server[oid]
if (excluded is not None and server == excluded) or loads[server] >= capacity[server]:
return False
else:
server = get_server(excluded)
if server is None:
return False
version += 1
conn[cid] = (server, oid, version)
loads[server] += 1
push_server(server)
if oid not in obj_server:
obj_server[oid] = server
obj_count[oid] = 0
obj_count[oid] += 1
server_queues[server].append((cid, version))
log.append(f'{cid} {server}')
return True
for req in requests:
parts = req.split()
if not parts:
continue
op = parts[0]
if op == 'CONNECT':
cid = parts[1]
oid = parts[2]
place_connection(cid, oid)
elif op == 'DISCONNECT':
cid = parts[1]
if cid in conn:
server, oid, _ = conn.pop(cid)
loads[server] -= 1
push_server(server)
obj_count[oid] -= 1
if obj_count[oid] == 0:
del obj_count[oid]
del obj_server[oid]
else: # SHUTDOWN
s = int(parts[1])
evicted = []
q = server_queues[s]
while q:
cid, ver = q.popleft()
state = conn.get(cid)
if state is not None and state[0] == s and state[2] == ver:
evicted.append((cid, state[1]))
for cid, oid in evicted:
del conn[cid]
obj_count[oid] -= 1
if obj_count[oid] == 0:
del obj_count[oid]
del obj_server[oid]
loads[s] = 0
for cid, oid in evicted:
place_connection(cid, oid, excluded=s)
push_server(s)
return log
Time complexity: O((q + e) log m) overall, where q is the number of requests and e is the total number of evicted connections processed across all shutdowns. This is output-sensitive because successful re-routes also generate log entries.. Space complexity: O(m + k), where k is the number of connection records stored across active maps and per-server arrival queues..
Hints
- During shutdown, remove every active connection from that server before rerouting begins; then rebuild stickiness as reroutes succeed.
- A per-server queue of arrivals plus version numbers is a practical way to recover the correct eviction order even after disconnects and earlier moves.