Stripe OA 面试真题解析：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.

这道 Stripe OA 题本质上是一个带约束的负载均衡模拟题，需要按顺序处理 CONNECT、DISCONNECT、SHUTDOWN 三类事件，并维护每个目标服务器的活跃连接数、连接到目标的映射，以及 objectId 到目标的绑定关系。核心规则是：优先选择当前负载最小的目标，负载相同时选编号更小的目标；如果某个 objectId 已经在某台服务器上活跃，则后续同 objectId 的连接必须继续路由到同一台；当服务器达到容量上限时要跳过该服务器，若所有可选服务器都满则拒绝连接；遇到 SHUTDOWN 时则需要先移除该目标上的所有活跃连接，再按连接 ID 顺序重新投递并记录重新路由后的日志。实现上通常用哈希表保存连接状态、对象归属和每台服务器的当前连接集合，整体是典型的细节模拟题。