Quick Overview

This question evaluates understanding of randomized selection, efficient in-memory data structures, and API/state management for a fixed-capacity load balancer that must support addNode, removeNode, and uniform random routing while handling duplicates, removals, and empty-state behavior.

Implement a random fixed-size load balancer

Company: Revolut

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem: Build a simple load balancer Implement a minimal in-memory load balancer that routes each incoming request to **one backend node chosen uniformly at random**. ### Requirements - The load balancer maintains a **set of backend nodes** (e.g., strings or IDs). - The number of nodes is bounded by a fixed maximum capacity `K`. - Support these operations: 1. `addNode(nodeId)` - Adds a node if it is not already present. - If the load balancer is at capacity `K`, define and document what happens (e.g., reject the add / throw). 2. `removeNode(nodeId)` - Removes the node if present; otherwise no-op. 3. `route()` (or `getNodeForRequest()`) - Returns a node chosen **uniformly at random** from the currently active nodes. - If there are **no nodes**, define and document what happens (e.g., return null / throw). ### Constraints / Edge cases to handle - Adding duplicates. - Removing a non-existent node. - Routing when empty. - Keeping `route()` efficient (ideally O(1)). ### Deliverable Describe the data structures and implement the API (language-agnostic or Java-style).

Quick Answer: This question evaluates understanding of randomized selection, efficient in-memory data structures, and API/state management for a fixed-capacity load balancer that must support addNode, removeNode, and uniform random routing while handling duplicates, removals, and empty-state behavior.

Implement a minimal in-memory load balancer that routes each incoming request to one backend node chosen uniformly at random, with a fixed maximum capacity. Because `route()` is random, this challenge drives the load balancer through a deterministic, seeded simulation so the behaviour is reproducible. Implement `solution(operations, capacity, seed)`: - `operations` is a list of `[op, arg]` pairs: - `["add", nodeId]` -> `addNode(nodeId)` - `["remove", nodeId]` -> `removeNode(nodeId)` - `["route", null]` -> `route()` - `capacity` (K) is the maximum number of active nodes. - `seed` seeds the random generator used by `route()`. Return a list with one result per operation: - **addNode** -> `True` if the node was added, `False` if it was rejected (already present, or already at capacity K). - **removeNode** -> `True` if the node was removed, `False` if it was not present (no-op). - **route** -> the chosen node id, or `None` if there are currently no active nodes. Design target: keep `addNode`, `removeNode`, and `route()` all O(1). **Edge cases to handle:** adding duplicates, removing a non-existent node, routing when empty, and rejecting adds at capacity. **Hint on the O(1) design:** keep a list of node ids for O(1) random indexing, plus a hash map from node id to its index in the list. To remove in O(1), swap the target with the last element, pop the last, and fix the moved element's index in the map.

Constraints

  • 0 <= number of operations <= 10^5
  • 1 <= capacity (K) <= 10^4
  • Node ids are non-empty strings (or comparable hashable ids).
  • addNode at capacity K is rejected (returns False).
  • removeNode on an absent node is a no-op (returns False).
  • route() on an empty set returns None.
  • Each operation should run in O(1) amortized time.

Examples

Input: ([['add', 'A'], ['add', 'B'], ['add', 'A'], ['route', None], ['remove', 'B'], ['remove', 'B'], ['route', None]], 2, 42)

Expected Output: [True, True, False, 'A', True, False, 'A']

Explanation: Add A and B (capacity 2). Adding A again is a duplicate -> False. route() with seed 42 returns 'A'. Remove B -> True; removing B again is a no-op -> False. With only A left, route() returns 'A'.

Input: ([['route', None]], 3, 1)

Expected Output: [None]

Explanation: Routing when there are no active nodes returns None.

Hints

  1. Maintain a flat list of active node ids so you can pick a random one in O(1) via an index.
  2. Maintain a hash map node_id -> index_in_list for O(1) membership checks and removals.
  3. To remove a node in O(1) without shifting, swap it with the last element, pop the last, and update the swapped element's index in the map.
  4. Guard the three edge cases explicitly: duplicate add, at-capacity add, remove-of-absent, and route-when-empty.

Loading coding console...