Katkat
Back

Implement Datacenter Router Commands

AmazonSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage stateful data structures, perform geometric calculations (Haversine formula), and implement multi-level sorting logic to simulate router command processing.

Problem Statement

You are building a control plane for a datacenter network. You must maintain a registry of routers and process a series of commands to route traffic to the nearest available router.

Each router is defined by its id (string), latitude (float), longitude (float), and capacity (int, current available bandwidth).

Implement a RouterManager class with the following methods:

  1. add_router(id, lat, lon, capacity): Adds a new router to the registry. If the id exists, update its details.
  2. remove_router(id): Removes the router from the registry.
  3. route_request(lat, lon, required_capacity): Returns the id of the router that meets the required_capacity, is closest to the given coordinates (using the Haversine formula), and has the smallest id as a tie-breaker. If no router meets the requirement, return None. If a router is chosen, decrement its capacity by required_capacity.

Haversine Formula

Use R = 6371 km as the Earth's radius. The distance d between two points (lat1, lon1) and (lat2, lon2) (in radians) is: a = sin^2(dlat/2) + cos(lat1) * cos(lat2) * sin^2(dlon/2) d = 2 * R * atan2(sqrt(a), sqrt(1-a))

Example

manager = RouterManager()
manager.add_router("r1", 40.71, -74.00, 100)
manager.add_router("r2", 34.05, -118.24, 100)
# Request at 40.75, -73.98
# Returns "r1" because it is closer to the target.
print(manager.route_request(40.75, -73.98, 50))

Constraints

  • Number of routers: up to 10^4.
  • Number of requests: up to 10^5.
  • lat is in [-90, 90], lon is in [-180, 180].

Hints

Hint 1

Pre-convert latitudes and longitudes to radians once when the router is added to avoid repeated conversions during distance calculations.

Hint 2

Since you need to find the 'nearest' router for every request, consider if a linear scan of all routers is acceptable given the constraints, or if a spatial indexing structure (like a KD-Tree) is required.

Hint 3

Ensure you handle the tie-breaking condition (lexicographically smallest ID) by including it in your sorting criteria or min-heap comparison logic.

Follow-up questions

  • How would the design change if thousands of requests arrived concurrently, requiring thread-safe updates to the router capacities?
  • If we needed to perform range queries (e.g., 'find all routers within 50km'), what data structure would you use to optimize performance?
  • How would you handle a scenario where a router's capacity is updated dynamically based on real-time network traffic patterns?