Request Routing System

Question

Build a simplified request routing system for a globally distributed cloud service provider (e.g., a global payment processing platform). The system processes a sequence of commands from stdin and returns responses to stdout.

Part 1 – Datacenter Registry & Health Management

REGISTER <name> <latitude> <longitude> <capacity>: Register a new datacenter. Validation rules: latitude must be in [-90, 90], longitude must be in [-180, 180], capacity must be strictly > 0, and name must be globally unique. On success, the datacenter is initialized with load = 0 and healthy = true. Returns "OK" or "ERROR".

SET_HEALTHY <name> <true|false>: Update the health status of an existing datacenter. Returns "OK" if the datacenter exists, "ERROR" otherwise.

Part 2 – Distance Calculation

DISTANCE <lat1> <lon1> <lat2> <lon2>: Calculate the great-circle distance between two geographic points using the Haversine formula with Earth radius R = 6371 km. Both coordinate pairs must be valid. Return the distance rounded to the nearest whole integer, or "ERROR" if any coordinate is invalid.

Haversine pseudocode (provided in the problem):

Convert latitudes/longitudes to radians
delta_lat = (lat2 - lat1) * π/180; delta_lon = (lon2 - lon1) * π/180
a = sin²(delta_lat/2) + cos(lat1_rad) * cos(lat2_rad) * sin²(delta_lon/2)
distance = 2 * R * arcsin(sqrt(a))

Part 3 – Proximity-Based Routing

ROUTE <user_lat> <user_lon>: Route a user request to the optimal datacenter. User coordinates must be valid (else ERROR). Routing logic:

Filter out all unhealthy datacenters.
Sort remaining healthy datacenters by distance to user (ascending); break ties alphabetically by name.
Iterate the sorted list and allocate to the first datacenter with available capacity (current_load < capacity); increment its load by 1.
Output format if allocated: <AllocatedName> <DistanceToUser> <comma-separated list of all healthy datacenter names in sorted order>
Output format if no healthy datacenter has available capacity: None <comma-separated list of all healthy datacenter names>
Output format if zero healthy datacenters exist: NONE (or NONE 0 per one variant)

All coordinates (latitude, longitude, capacity) are integers. There are 20 test cases total distributed across the three parts. The OA is timed (~1 hour).

5. Output format if no healthy datacenter has available capacity: None 6. Output format if zero healthy datacenters exist: NONE (or NONE 0 per one variant) All coordinates (latitude, longitude, capacity) are integers. There are 20 test cases total distributed across the three parts. The OA is timed (~1 hour).

AceOffer · Accepted Answer

Build a simplified request routing system for a globally distributed cloud service provider (e.g., a global payment processing platform). The system processes a sequence of commands from stdin and returns responses to stdout.

Part 1 – Datacenter Registry & Health Management

REGISTER <name> <latitude> <longitude> <capacity>: Register a new datacenter. Validation rules: latitude must be in [-90, 90], longitude must be in [-180, 180], capacity must be strictly > 0, and name must be globally unique. On success, the datacenter is initialized with load = 0 and healthy = true. Returns "OK" or "ERROR".

SET_HEALTHY <name> <true|false>: Update the health status of an existing datacenter. Returns "OK" if the datacenter exists, "ERROR" otherwise.

Part 2 – Distance Calculation

DISTANCE <lat1> <lon1> <lat2> <lon2>: Calculate the great-circle distance between two geographic points using the Haversine formula with Earth radius R = 6371 km. Both coordinate pairs must be valid. Return the distance rounded to the nearest whole integer, or "ERROR" if any coordinate is invalid.

Haversine pseudocode (provided in the problem):

Convert latitudes/longitudes to radians
delta_lat = (lat2 - lat1) * π/180; delta_lon = (lon2 - lon1) * π/180
a = sin²(delta_lat/2) + cos(lat1_rad) * cos(lat2_rad) * sin²(delta_lon/2)
distance = 2 * R * arcsin(sqrt(a))

Part 3 – Proximity-Based Routing

ROUTE <user_lat> <user_lon>: Route a user request to the optimal datacenter. User coordinates must be valid (else ERROR). Routing logic:

Filter out all unhealthy datacenters.
Sort remaining healthy datacenters by distance to user (ascending); break ties alphabetically by name.
Iterate the sorted list and allocate to the first datacenter with available capacity (current_load < capacity); increment its load by 1.
Output format if allocated: <AllocatedName> <DistanceToUser> <comma-separated list of all healthy datacenter names in sorted order>
Output format if no healthy datacenter has available capacity: None <comma-separated list of all healthy datacenter names>
Output format if zero healthy datacenters exist: NONE (or NONE 0 per one variant)

All coordinates (latitude, longitude, capacity) are integers. There are 20 test cases total distributed across the three parts. The OA is timed (~1 hour).

5. Output format if no healthy datacenter has available capacity: None 6. Output format if zero healthy datacenters exist: NONE (or NONE 0 per one variant) All coordinates (latitude, longitude, capacity) are integers. There are 20 test cases total distributed across the three parts. The OA is timed (~1 hour). Edge cases probed: Registering a datacenter with a duplicate name (should return ERROR); Registering with latitude exactly at boundary values: -90, 90 (valid) vs 91 (invalid); Registering with capacity = 0 (invalid; must be strictly > 0); SET_HEALTHY on a datacenter name that does not exist (ERROR); DISTANCE with an invalid coordinate, e.g., lat=91 (ERROR); DISTANCE between identical points (output: 0); ROUTE when all healthy datacenters are at full capacity (output: None + list of healthy nodes); ROUTE tie-breaking: two datacenters at equal distance sorted alphabetically by name; Load tracking: once a datacenter reaches capacity, subsequent ROUTE calls must skip it

Request Routing System

Problem Overview

What Reports Emphasize

Practice

More Stripe Questions

Every question in the Stripe catalog gets this depth