Request Routing System (REGISTER / DISTANCE / ROUTE)

HackerRank OA. Build a data-center router: register datacenters with lat/lon and capacity, support health toggles, compute great-circle distance, and route incoming requests to the nearest healthy datacenter with available capacity. Requirements A command-driven control plane for a globally distributed request router. Read commands from standard input and emit exactly one line of output per command. On any validation failure, emit ERROR and leave system state unchanged. The problem is split into three progressive parts, each building on the previous. Datacenter model: name (unique string), lat, lon, capacity (positive int), healthy (bool, defaults true), load (current routed requests, defaults 0). Constants: Earth radius R = 6371 km; latitude [-90, 90] inclusive; longitude [-180, 180] inclusive; capacity strictly > 0. Command summary Command Arguments Output on success REGISTER <name> <lat> <lon> <capacity> OK SET_HEALTHY <name> <true|false> OK DISTANCE <lat1> <lon1> <lat2> <lon2> <integer km> ROUTE <lat> <lon> <chosen|None> [distance] <candidate,list> Part 1 — REGISTER and SET_HEALTHY REGISTER <name> <lat> <lon> <capacity>: create a datacenter. Validate -90 <= lat <= 90, -180 <= lon <= 180, capacity > 0, and a unique name. On any validation failure emit ERROR. Default health is healthy; default current load is 0. SET_HEALTHY <name> <bool>: toggle health for an existing datacenter, ERROR if the name is unknown. A datacenter's load is preserved across health transitions — marking it unhealthy does NOT drain its load. def register(self, name: str, lat: float, lon: float, capacity: int) -> str: ... # Returns "OK", or "ERROR" if lat∉[-90,90], lon∉[-180,180], capacity<=0, or name already exists. # Validate ALL inputs before mutating state so a rejected command leaves the registry untouched. def set_healthy(self, name: str, healthy: bool) -> str: ... # Returns "OK", or "ERROR" if no datacenter with that name exists. Does not touch load. Part 2 — DISTANCE DISTANCE <lat1> <lon1> <lat2> <lon2>: emit the great-circle distance in km, using Earth radius 6371, rounded to the nearest integer. Validate each coordinate (same bounds as Part 1); ERROR on invalid input. Use the Haversine formula. def haversine_km(lat1: float, lon1: float, lat2: float, lon2: float) -> int: ... # Pure helper, no router state. Convert degrees to radians first. # a = sin²(Δlat/2) + cos(lat1)·cos(lat2)·sin²(Δlon/2) # c = 2·atan2(√a, √(1−a)); return round(R * c) with R = 6371. def distance(lat1: float, lon1: float, lat2: float, lon2: float) -> str: ... # Returns str(haversine_km(...)), or "ERROR" if any coordinate is out of range. Part 3 — ROUTE ROUTE <lat> <lon>: route a single client request from (lat, lon). Filter out unhealthy datacenters; sort the remaining by great-circle distance ascending (ties broken by name lexicographically ascending); pick the first whose load < capacity; increment its load by 1. ERROR if the client coordinates are out of range. Output format (on a valid request): <chosen-name-or-None> <distance-km-if-chosen> <candidate1,candidate2,...> chosen name is the picked datacenter, or the literal None if every healthy datacenter is at capacity. distance (rounded integer km to the chosen DC) is printed ONLY when a datacenter was chosen; omit the distance field entirely when the result is None. candidate list is the filtered-and-sorted healthy datacenter names, comma-joined with no spaces, printed regardless of whether one was chosen. def route(self, lat: float, lon: float) -> str: ... # "ERROR" if client coords out of range. Filter healthy → sort by (dist, name) → # first with load<capacity gets load+=1. Returns "<name> <dist> <candidates>", # or "None <candidates>" if all healthy DCs are at capacity. Examples REGISTER us-west 38 -122 100 -> OK REGISTER us-east 41 -74 150 -> OK REGISTER us-west 50 -100 50 -> ERROR # duplicate name REGISTER invalid-node 91 0 100 -> ERROR # lat out of range REGISTER invalid-cap 0 0 0 -> ERROR # capacity <= 0 SET_HEALTHY us-east false -> OK SET_HEALTHY fake-node true -> ERROR # unknown name DISTANCE 38 -122 41 -74 -> 4080 DISTANCE 0 0 0 0 -> 0 DISTANCE 91 0 0 0 -> ERROR ROUTE walkthrough (two unit-capacity nodes at the same point, one unhealthy node): REGISTER node-A 0 0 1 -> OK REGISTER node-B 0 0 1 -> OK REGISTER node-C 10 10 100 -> OK SET_HEALTHY node-C false -> OK ROUTE 0 0 -> node-A 0 node-A,node-B # node-C filtered out; A,B tie at dist 0, name tiebreak; A chosen, load→1 ROUTE 0 0 -> node-B 0 node-A,node-B # A at capacity, walk to B; B chosen, load→1 ROUTE 0 0 -> None node-A,node-B # both at capacity; print None, omit distance, still print candidates Notes Two community reports flag the prompt as long and verbose; reading speed is the limiter. The output format combines OK / ERROR lines with structured ROUTE lines — keep your IO disciplined. Floating-point precision on Haversine has caused candidates to lose case grading. Round consistently. Use round() (nearest integer), not int() (truncation): for SF→NY the raw value is ~4079.7, which round() yields 4080 (the expected answer) while int() would truncate to 4079. Canonical Haversine: a = sin²(Δφ/2) + cos(φ₁)·cos(φ₂)·sin²(Δλ/2), then c = 2·atan2(√a, √(1−a)) and d = R·c with R = 6371 km. Convert lat/lon to radians first. Prefer atan2(√a, √(1−a)) over asin(√a): atan2 is numerically stable across the full [0, π] range, while asin(√a) loses precision near antipodal points where a → 1. (An alternative boundary check is to clamp a to [0, 1] before sqrt to absorb floating-point overshoot.) The Haversine form (not the spherical law of cosines) is the standard choice precisely because it stays numerically stable for short distances. Design choices that carry across parts Key the registry by name in a dict — O(1) duplicate-name check, and ROUTE iterates its values. Keep load on the Datacenter object itself, so SET_HEALTHY need not touch it and ROUTE's selector can mutate it in place with no external bookkeeping. Use a single try/except-on-parse dispatcher (ValueError / IndexError → ERROR); the same pattern extends verbatim as Parts 2 and 3 add commands. ROUTE is O(N log N) per call (dominated by the sort), O(N) space for the scored list, where N is the number of healthy datacenters. REGISTER and SET_HEALTHY are both O(1). Reference implementation A single Router owns the registry (a dict keyed by name); Datacenter is a thin __slots__ record holding per-node state. haversine_km is a pure module-level helper (no router state) so ROUTE reuses it directly with no re-implementation. The dispatcher validates by parse — any ValueError / IndexError collapses to ERROR, and every handler fully validates before mutating, so a rejected command leaves state untouched. import sys, math R_KM = 6371 class Datacenter: __slots__ = ("name", "lat", "lon", "capacity", "healthy", "load") def __init__(self, name: str, lat: float, lon: float, capacity: int): self.name = name self.lat = lat self.lon = lon self.capacity = capacity self.healthy = True self.load = 0 def haversine_km(lat1: float, lon1: float, lat2: float, lon2: float) -> int: p1, p2 = math.radians(lat1), math.radians(lat2) dp = math.radians(lat2 - lat1) dl = math.radians(lon2 - lon1) a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2 c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a)) return round(R_KM * c) class Router: def __init__(self) -> None: self.datacenters: dict[str, Datacenter] = {} def register(self, name: str, lat: float, lon: float, capacity: int) -> str: if not (-90 <= lat <= 90): return "ERROR" if not (-180 <= lon <= 180): return "ERROR" if capacity <= 0: return "ERROR" if name in self.datacenters: return "ERROR" self.datacenters[name] = Datacenter(name, lat, lon, capacity) return "OK" def set_healthy(self, name: str, healthy: bool) -> str: dc = self.datacenters.get(name) if dc is None: return "ERROR" dc.healthy = healthy return "OK" def distance(self, lat1: float, lon1: float, lat2: float, lon2: float) -> str: for lat in (lat1, lat2): if not (-90 <= lat <= 90): return "ERROR" for lon in (lon1, lon2): if not (-180 <= lon <= 180): return "ERROR" return str(haversine_km(lat1, lon1, lat2, lon2)) def route(self, lat: float, lon: float) -> str: if not (-90 <= lat <= 90) or not (-180 <= lon <= 180): return "ERROR" healthy = [dc for dc in self.datacenters.values() if dc.healthy] scored = [(haversine_km(lat, lon, dc.lat, dc.lon), dc.name, dc) for dc in healthy] scored.sort(key=lambda t: (t[0], t[1])) candidates = ",".join(name for _, name, _ in scored) for dist, name, dc in scored: if dc.load < dc.capacity: dc.load += 1 return f"{name} {dist} {candidates}" return f"None {candidates}" def main() -> None: router = Router() for line in sys.stdin: parts = line.strip().split() if not parts: continue cmd = parts[0] try: if cmd == "REGISTER": name, lat, lon, cap = parts[1], float(parts[2]), float(parts[3]), int(parts[4]) print(router.register(name, lat, lon, cap)) elif cmd == "SET_HEALTHY": name, flag = parts[1], parts[2].lower() == "true" print(router.set_healthy(name, flag)) elif cmd == "DISTANCE": a, b, c, d = map(float, parts[1:5]) print(router.distance(a, b, c, d)) elif cmd == "ROUTE": a, b = float(parts[1]), float(parts[2]) print(router.route(a, b)) else: print("ERROR") except (ValueError, IndexError): print("ERROR") Preparation Pre-write Haversine in your language of choice and validate against a public reference value (e.g. SFO ↔ JFK ≈ 4150 km). Drill command-dispatch interpreters: read a line, parse the verb, route to handler, emit output. Stand up tests for each command type — bad input, valid input, duplicate, ROUTE with no healthy DC. Pre-write Haversine once with explicit radian conversion + the atan2 form (or a min(1.0, a) clamp), then validate against two reference pairs (e.g. SFO ↔ JFK ≈ 4150 km, LAX ↔ SYD ≈ 12050 km) so you have a sanity check ready during the round.