Katkat
Back

Implement a Datacenter Request Router

StripeSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests the ability to manage stateful datacenter metadata and implement a routing algorithm that prioritizes proximity (Haversine distance) while respecting capacity constraints.

Datacenter Request Router

You are building a router that assigns incoming requests to the 'best' available datacenter. Each datacenter is defined by its name, latitude, longitude, and max capacity. A request is defined by its latitude, longitude, and a unique identifier.

Requirements

  1. add_datacenter(name, lat, lon, capacity): Register a new datacenter.
  2. route_request(request_id, lat, lon): Assign a request to an available datacenter based on the following rules:
    • Only datacenters with current_load < capacity are eligible.
    • Among eligible datacenters, select the one with the smallest Haversine distance to the request.
    • If distances are equal, select the datacenter whose name is lexicographically smaller.
    • If a request is assigned, increment that datacenter's load and return its name.
    • If no datacenters are available, return None.

Haversine Formula

To calculate the distance between two points (lat1, lon1) and (lat2, lon2) in radians, use: a = sin²(Δlat/2) + cos(lat1) * cos(lat2) * sin²(Δlon/2) c = 2 * atan2(√a, √(1−a)) d = R * c (Use R = 6371 km)

Constraints

  • Latitudes: [-90, 90], Longitudes: [-180, 180]
  • request_id is a unique string.
  • Max datacenters: 1000.

Examples

router = RequestRouter()
router.add_datacenter("US-East", 37.7, -122.4, 10)
router.add_datacenter("EU-West", 51.5, -0.1, 10)

# Request in London (51.5, -0.1)
print(router.route_request("req1", 51.5, -0.1))
# Output: "EU-West"

Hints

Hint 1

Convert latitude and longitude coordinates from degrees to radians before performing trigonometric calculations.

Hint 2

Maintain a dictionary or hash map to store datacenter metadata and their current load for O(1) lookups.

Hint 3

Since the number of datacenters is small, you can iterate through all available datacenters for every request to find the minimum distance.

Follow-up questions

  • How would you optimize the search if the number of datacenters increased to 1,000,000?
  • What changes are needed if the datacenter capacity is dynamic and can be updated via a separate API call?
  • How would you implement load balancing if you wanted to distribute requests evenly among datacenters at the same distance, rather than just picking the lexicographical smallest?