Stripe OA Interview Problem: Load Balancing Jupyter Server Requests

The notebook platform at Stripe is based on Jupyter. It does not perform well with a large number of active connections, so we want to route developers to different Jupyter servers depending on load.

In this multi-part problem, implement route_requests, a load balancer that determines the target server for each incoming request.

Function description

• int numTargets: the number of target Jupyter servers.
• int maxConnectionsPerTarget: the maximum number of active connections allowed on a target server.
• string requests[n]: incoming request lines. Each line uses one of these schemas:
  • action,connectionId,userId,objectId
  • action,targetIndex

Return value

• string[n]: a log of each CONNECT request in the format connectionId,userId,targetIndex. The target index is 1-based.

Part 1: Basic load balancing

For each incoming request, choose the target with the smallest number of active requests. If there is a tie, choose the smaller target index. Process requests in order.

Example

CONNECT,conn1,userA,obj1
CONNECT,conn2,userB,obj2

The result should route userA to target 1 and userB to target 2.

Part 2: Modeling disconnection

Handle CONNECT and DISCONNECT. A disconnect removes the active connection from its target. You may assume every DISCONNECT corresponds to a previously connected client.

Part 3: Routing based on object ID

If a client connects with an object ID that is already active on some target, it must be routed to that same target to preserve shared notebook state.

Part 4: Target size limits

If a target has reached maxConnectionsPerTarget, it cannot receive new connections. If every eligible target is full, reject the connection and do not add it to the log.

Part 5: Target shutdown

When a SHUTDOWN,targetIndex request arrives, evict all active connections from that target. Re-route the evicted connections one by one in connection ID order using the same balancing and object-ID rules. Log any new connections created during this process.

Example

CONNECT,conn1,userA,obj1
CONNECT,conn2,userB,obj2
SHUTDOWN,1
CONNECT,conn3,userC,obj3

The output should log the original connections, then the re-routed evicted connection, and finally the last connection.

This Stripe OA problem is a simulation-heavy load balancing task. You must process CONNECT, DISCONNECT, and SHUTDOWN requests in order while maintaining per-target active counts, connection-to-target mapping, and objectId affinity. The main rules are: choose the least-loaded target with tie-breaking by smaller index; keep all active connections for the same objectId on the same target; reject CONNECT requests when every eligible target is at capacity; and on SHUTDOWN, evict all active connections from the target and reroute them in connection ID order. A correct solution typically uses hash maps to track connections, object ownership, and per-target active sets, plus careful handling of rerouting and capacity checks.