Implement Datacenter Router Commands
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Implement `process_commands(commands) -> list[str]` for a datacenter router simulator. The input is a list of command strings, and the function must return one output string per command in the same order.
Assume commands are syntactically well-formed, command names are uppercase, datacenter names contain no spaces, latitudes/longitudes are numeric, and capacities are integers.
Supported commands:
1. `REGISTER name lat lon capacity`
Register a new datacenter.
Validation rules: all must pass, otherwise return `ERROR` and do not register anything.
- `lat` must be in `[-90, 90]`.
- `lon` must be in `[-180, 180]`.
- `capacity` must be greater than `0`.
- `name` must not already be registered.
On success, store the datacenter with:
- `healthy = true`
- `load = 0`
- the given `capacity`
Return `OK`.
2. `SET_HEALTHY name true|false`
Update the health status of an existing datacenter.
- If `name` does not exist, return `ERROR`.
- Otherwise, update the health flag and return `OK`.
3. `DISTANCE lat1 lon1 lat2 lon2`
Compute the Haversine distance between two coordinates.
Validation rules:
- `lat1` and `lat2` must be in `[-90, 90]`.
- `lon1` and `lon2` must be in `[-180, 180]`.
If any coordinate is invalid, return `ERROR`.
Use Earth radius `R = 6371 km`. Return the distance rounded to the nearest integer, as a string.
4. `ROUTE lat lon`
Route one request from the given client coordinate to a healthy datacenter using distance-based load balancing. Assume the route coordinates are valid.
Algorithm:
- Filter to datacenters where `healthy == true`.
- Compute the Haversine distance from the client coordinate to each healthy datacenter.
- Sort healthy datacenters by ascending distance; break ties alphabetically by datacenter name.
- Iterate through the sorted list and select the first datacenter whose `load < capacity`.
- The comma-separated healthy-name list must include all healthy datacenters in the sorted order, including datacenters that are already full.
Return format:
- If a datacenter is selected, increment its load by `1` and return `"<name> <rounded_distance> <healthy_names_csv>"`.
- If no healthy datacenter has remaining capacity, return `"None <healthy_names_csv>"`.
- If there are no healthy datacenters, return `"None"`.
Example 1:
Input commands:
```text
REGISTER us-west 38 -122 100
REGISTER us-east 41 -74 150
REGISTER us-west 50 -100 50
REGISTER invalid-node 91 0 100
REGISTER invalid-cap 0 0 0
SET_HEALTHY us-east false
SET_HEALTHY fake-node true
```
Output:
```text
OK
OK
ERROR
ERROR
ERROR
OK
ERROR
```
Example 2:
Input commands:
```text
DISTANCE 38 -122 41 -74
DISTANCE 0 0 0 0
DISTANCE 91 0 0 0
```
Output:
```text
4080
0
ERROR
```
Example 3:
Input commands:
```text
REGISTER node-A 0 0 1
REGISTER node-B 0 0 1
REGISTER node-C 10 10 100
SET_HEALTHY node-C false
ROUTE 0 0
ROUTE 0 0
ROUTE 0 0
```
Output:
```text
OK
OK
OK
OK
node-A 0 node-A,node-B
node-B 0 node-A,node-B
None node-A,node-B
```
Quick Answer: This question evaluates proficiency in stateful command processing, input validation, geospatial computation (Haversine distance), deterministic sorting and tie-breaking, distance-based load balancing, and data modeling for a datacenter simulator.
Implement a function `solution(commands)` for a datacenter router simulator. The input is a list of command strings, and the function must return a list of output strings with exactly one result per command in the same order.
The system stores datacenters by name. Each datacenter has latitude, longitude, capacity, health status, and current load.
Supported commands:
1. `REGISTER name lat lon capacity`
- Register a new datacenter.
- Validation rules: latitude must be in `[-90, 90]`, longitude must be in `[-180, 180]`, capacity must be greater than `0`, and the name must not already exist.
- If validation fails, return `ERROR` and do not register anything.
- On success, store the datacenter with `healthy = true`, `load = 0`, and the given capacity, then return `OK`.
2. `SET_HEALTHY name true|false`
- Update the health flag of an existing datacenter.
- If the datacenter does not exist, return `ERROR`.
- Otherwise update its health status and return `OK`.
3. `DISTANCE lat1 lon1 lat2 lon2`
- Compute the Haversine distance between two coordinates using Earth radius `R = 6371 km`.
- Validation rules: `lat1` and `lat2` must be in `[-90, 90]`; `lon1` and `lon2` must be in `[-180, 180]`.
- If any coordinate is invalid, return `ERROR`.
- Otherwise return the distance rounded to the nearest integer as a string.
4. `ROUTE lat lon`
- Route one request from the given client location. Assume these route coordinates are always valid.
- Consider only datacenters with `healthy == true`.
- Compute the Haversine distance from the client to every healthy datacenter.
- Sort healthy datacenters by ascending distance; if distances tie, sort alphabetically by name.
- From that sorted order, select the first datacenter whose `load < capacity`.
- The healthy datacenter CSV in the output must include all healthy datacenters in the sorted order, even if some are already full.
- If a datacenter is selected, increment its load by 1 and return `"<name> <rounded_distance> <healthy_names_csv>"`.
- If there are healthy datacenters but all are full, return `"None <healthy_names_csv>"`.
- If there are no healthy datacenters, return `"None"`.
You may assume commands are syntactically well-formed, command names are uppercase, datacenter names contain no spaces, numeric values can be parsed successfully, and capacities are integers.
Constraints
- 0 <= len(commands) <= 10^4
- At most 10^4 datacenters will be registered
- All commands are syntactically well-formed
- Use the Haversine formula with Earth radius R = 6371 km
- Round returned distances to the nearest integer
Examples
Input: ([],)
Expected Output: []
Explanation: No commands means no output strings.
Input: (['REGISTER us-west 38 -122 100', 'REGISTER us-east 41 -74 150', 'REGISTER us-west 50 -100 50', 'REGISTER invalid-node 91 0 100', 'REGISTER invalid-cap 0 0 0', 'SET_HEALTHY us-east false', 'SET_HEALTHY fake-node true'],)
Expected Output: ['OK', 'OK', 'ERROR', 'ERROR', 'ERROR', 'OK', 'ERROR']
Explanation: The first two registrations succeed. Then there is a duplicate name, an invalid latitude, and an invalid capacity. Setting `us-east` unhealthy succeeds, but updating a missing node fails.
Input: (['DISTANCE 38 -122 41 -74', 'DISTANCE 0 0 0 0', 'DISTANCE 91 0 0 0', 'DISTANCE -90 -180 90 180'],)
Expected Output: ['4080', '0', 'ERROR', '20015']
Explanation: The first command computes a valid great-circle distance, the second is zero, the third has an invalid latitude, and the last is half the Earth's circumference.
Input: (['REGISTER node-A 0 0 1', 'REGISTER node-B 0 0 1', 'REGISTER node-C 10 10 100', 'SET_HEALTHY node-C false', 'ROUTE 0 0', 'ROUTE 0 0', 'ROUTE 0 0'],)
Expected Output: ['OK', 'OK', 'OK', 'OK', 'node-A 0 node-A,node-B', 'node-B 0 node-A,node-B', 'None node-A,node-B']
Explanation: Nodes A and B are equally close, so alphabetical order breaks the tie. Each has capacity 1, so the third route finds healthy nodes but no remaining capacity.
Input: (['REGISTER solo 0 0 1', 'SET_HEALTHY solo false', 'ROUTE 0 0', 'SET_HEALTHY solo true', 'ROUTE 0 0', 'ROUTE 0 0'],)
Expected Output: ['OK', 'OK', 'None', 'OK', 'solo 0 solo', 'None solo']
Explanation: When the only datacenter is unhealthy, routing returns `None`. After re-enabling it, one request is routed successfully and the next finds the healthy node full.
Hints
- A hash map keyed by datacenter name makes REGISTER and SET_HEALTHY efficient.
- For each ROUTE command, build a list of healthy datacenters with their distances, sort by `(distance, name)`, then scan for the first one that still has capacity.