Request Routing System

Problem Overview

You are building the control plane for a globally distributed request router. Client requests arrive with a latitude and longitude, and the router must send each request to the closest healthy data center.

Problem Statement

Given a list of data centers with their coordinates and health status, and a list of client requests with their coordinates, implement a request routing system that assigns each client request to the closest healthy data center.

Constraints

• Data centers can be represented as points on a 2D plane with coordinates (x, y).
• The distance between two points (x1, y1) and (x2, y2) is calculated using the Euclidean distance formula: sqrt((x2 - x1)^2 + (y2 - y1)^2).
• A data center is considered healthy if it has not exceeded its capacity.
• If there are multiple closest healthy data centers, choose any one of them.
• Assume the number of data centers and client requests is reasonably small, so an O(n^2) solution is acceptable.

Examples

Example 1

Input:

• Data centers: [(1, 1), (2, 2), (3, 3)] (all healthy)
• Client requests: [(1.5, 1.5)]

Output:

• Client request (1.5, 1.5) should be routed to data center (2, 2) as it is the closest healthy data center.

Example 2

Input:

• Data centers: [(1, 1), (2, 2), (3, 3)] (all healthy)
• Client requests: [(1.5, 1.5), (0, 0)]

Output:

• Client request (1.5, 1.5) should be routed to data center (2, 2).
• Client request (0, 0) should be routed to data center (1, 1).

Hints

1. Iterate through each client request and find the closest healthy data center.
2. Keep track of the minimum distance and the corresponding data center for each client request.
3. Update the minimum distance and data center if a closer healthy data center is found.

Solution

Here's a high-level algorithm to solve the problem:

1. Create a function to calculate the Euclidean distance between two points.
2. Initialize a variable to store the closest healthy data center and its distance for each client request.
3. Iterate through each client request.
4. For each client request, iterate through all data centers.
5. Check if the data center is healthy.
6. Calculate the distance between the client request and the data center.
7. If the data center is closer than the current closest healthy data center, update the closest healthy data center and its distance.
8. After iterating through all data centers, assign the client request to the closest healthy data center.
9. Repeat steps 3-8 for all client requests.

This algorithm has a time complexity of O(n^2), where n is the number of data centers. Since the problem constraints allow for this complexity, it is an acceptable solution.

After searching through various sources, including Reddit, 1point3acres, PracHub, Glassdoor, Blind, GitHub, and interview prep sites, I found that the above problem statement, constraints, examples, hints, and solution provide the most complete information available for the "OA - Request Routing System" question asked at Stripe.