PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • medium
  • Stripe
  • Coding & Algorithms
  • Software Engineer

Simulate sticky load balancer with shutdown

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Problem Implement a simulator for a load balancer that routes long-lived WebSocket connections across **m** backend servers. You receive a sequence of textual requests. The simulator must maintain internal state (active connections) and output a **log of successful routings**. You must support these request types (each part includes all prior rules): ### State you must track - For each active `connectionId`: which `serverIndex` it is currently on, and its `objectId`. - For each server: current number of active connections. - Stickiness: active connections sharing the same `objectId` must be routed to the same server (details below). ### Routing rules (applies to any time you need to place a connection) When routing a connection to a server, choose among **eligible servers**: 1. The server with the **fewest active connections**. 2. Break ties by **smaller `serverIndex`**. A server is **ineligible** if it is at capacity. ### Request formats Assume servers are indexed `0 .. m-1`. - `CONNECT connectionId objectId` - `DISCONNECT connectionId` - `SHUTDOWN serverIndex` ### Part 1 — Basic load balancing (`CONNECT` only) For each `CONNECT`, route the new connection using the routing rules above and **log** the successful routing. ### Part 2 — Disconnection (`DISCONNECT`) `DISCONNECT connectionId` removes that active connection (if present) and decrements that server’s load. - `DISCONNECT` produces **no log entry**. ### Part 3 — Object stickiness Each `CONNECT` includes an `objectId`. - If there is **already an active connection** with the same `objectId`, the new connection **must** be routed to the **same server** as those active connections, even if it is not the least loaded. - If there is **no active connection** for that `objectId`, use normal load balancing. ### Part 4 — Server capacity limits You are given an array `capacity[m]`, where `capacity[i]` is the maximum allowed active connections on server `i`. - A server at capacity cannot accept new connections. - If a `CONNECT` has **no eligible server**, it is **rejected**: **no log entry** and **no state change**. - If stickiness requires routing to a server that is full, the `CONNECT` is also **rejected**. ### Part 5 — Server shutdown (`SHUTDOWN`) `SHUTDOWN s` temporarily takes server `s` out of service and evicts **all** active connections currently on `s`. - Evicted connections must be **re-routed one by one** using the **same rules as a new `CONNECT`** (including stickiness and capacity). - Each successful re-route produces a **log entry** (same format as `CONNECT`). - Rejected re-routes produce **no log entry**, and that connection is dropped (becomes inactive). - The shutdown server `s` is considered **unavailable as a target during the re-routing step**, and then becomes **available again immediately after all evictions are processed**, with load 0. - Process the evicted connections **in the order they originally connected to server `s`** (earliest first) to make the outcome deterministic. ## Output (log) Return the list of log entries in order. Each log entry should be: `connectionId serverIndex` Only successful `CONNECT` and successful re-routes during `SHUTDOWN` produce log lines. ## Assumptions / Notes - `connectionId` strings are unique among active connections at the time of `CONNECT`. - If `DISCONNECT` references a non-existent/ inactive `connectionId`, ignore it. ## Constraints (for choosing appropriate data structures) - `1 <= m <= 1e5` - `1 <= number of requests <= 2e5` - `0 <= capacity[i] <= 1e9` - IDs fit in typical string lengths (e.g., up to 50 chars).

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

You are given m backend servers indexed from 0 to m-1 and a list of requests. In this version, every request is of the form 'CONNECT connectionId'. When a connection arrives, route it to the eligible server with the fewest active connections. If multiple servers have the same load, choose the smaller server index. Every successful connection must be logged as 'connectionId serverIndex'. Return the full log in order.

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.

Hints

  1. Keep track of each server's current load.
  2. A min-heap of (load, serverIndex) helps you find the next target server quickly.

Part 2: Load Balancer with Disconnect

You are given m backend servers indexed from 0 to m-1 and a list of requests. Requests are either 'CONNECT connectionId' or 'DISCONNECT connectionId'. A CONNECT routes the new connection to the server with the fewest active connections, breaking ties by smaller server index, and logs 'connectionId serverIndex'. A DISCONNECT removes that active connection if it exists and decreases the server's load. DISCONNECT produces no log entry. Return the log of successful CONNECT operations.

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.

Hints

  1. You need a map from connectionId to its current server.
  2. After a disconnect, the least-loaded server can change, so update your heap lazily.

Part 3: Sticky Load Balancer by Object

You are given m backend servers indexed from 0 to m-1 and a list of requests. Requests are either 'CONNECT connectionId objectId' or 'DISCONNECT connectionId'. Route new connections using these rules: if there is already an active connection with the same objectId, the new connection must go to the same server as that object's active connections. Otherwise, choose the server with the fewest active connections, breaking ties by smaller server index. DISCONNECT removes an active connection if present. Only successful CONNECT operations are logged as 'connectionId serverIndex'. Return the log.

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.

Hints

  1. Track both connectionId -> (server, objectId) and objectId -> server.
  2. 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

You are given an array capacity where capacity[i] is the maximum number of active connections server i can hold. Requests are either 'CONNECT connectionId objectId' or 'DISCONNECT connectionId'. For a CONNECT, if the objectId is already active, the new connection must go to that same server. Otherwise, route to the eligible server with the fewest active connections, breaking ties by smaller server index. A server is eligible only if its current load is strictly less than its capacity. If no eligible server exists, reject the CONNECT: produce no log entry and make no state change. If stickiness points to a full server, reject the CONNECT as well. Return the log of successful CONNECT operations.

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.

Hints

  1. A min-heap still works, but now you must skip servers whose load reached capacity.
  2. For sticky objects, do not search the heap first; check the required server directly.

Part 5: Sticky Load Balancer with Shutdown

You are given an array capacity where capacity[i] is the maximum number of active connections on server i. Requests are 'CONNECT connectionId objectId', 'DISCONNECT connectionId', or 'SHUTDOWN serverIndex'. CONNECT and DISCONNECT behave as in the sticky, capacity-limited balancer. SHUTDOWN s works like this: first, all active connections currently on server s are evicted. Then, while server s is temporarily unavailable as a target, those evicted connections are re-routed one by one using the same rules as a fresh CONNECT. Process them in the order they arrived on server s, earliest first. Successful re-routes produce log entries; failed re-routes are dropped silently. After all evictions are processed, server s becomes available again with load 0. Return the full log of successful CONNECT operations and successful shutdown re-routes.

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.

Hints

  1. During shutdown, remove every active connection from that server before rerouting begins; then rebuild stickiness as reroutes succeed.
  2. 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.
Last updated: May 16, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Assign Reviewers from Changed Files - Stripe (medium)
  • Generate Account Email Notifications - Stripe (medium)
  • Calculate Transaction Fees - Stripe (medium)
  • Build an Account Transfer Ledger - Stripe (medium)
  • Implement Validation and String Compression - Stripe (hard)