Problem Description

You're tasked to build a request routing system for a global payment processing platform that handles transactions for millions of merchants worldwide. Your infrastructure spans multiple datacenters across continents to ensure low latency and high availability for payment processing.

You're tasked to build a request routing system. Your router must select the optimal datacenter based on geographic proximity, health status, and capacity constraints.

Input/Output Format

Your program reads commands from stdin and writes results to stdout. Each command is on a separate line.

Output Format Rules

• SUCCESS: Commands return OK or structured data as specified.
• ERROR: Commands return ERROR (no additional message).
• Lists: Comma-separated with no spaces (e.g., dc1,dc2,dc3).
• Boolean values: true or false (lowercase).

Part 1: Datacenter Registry and Health Management

Build the foundational data structures and APIs for managing datacenter registration and health status.

Requirements

• Implement datacenter registration with validation.
• Validate coordinates: latitude [-90, 90], longitude [-180, 180] (for simplicity you can assume these to be integers).
• Validate capacity: must be greater than 0.
• Prevent duplicate registrations.
• Support health status management.
• All datacenters initially registered as healthy with load = 0.

Commands to Implement

1. REGISTER

REGISTER <name> <latitude> <longitude> <capacity>

• Registers a new datacenter.
• Returns: OK or ERROR.
• Error cases:
  • Datacenter with same name already exists.
  • Invalid latitude (not in [-90, 90]).
  • Invalid longitude (not in [-180, 180]).
  • Invalid capacity (≤ 0).

2. SET_HEALTHY

SET_HEALTHY <name> <true|false>

• Sets datacenter health status.
• Returns: OK or ERROR.
• Error cases:
  • Datacenter does not exist.

Example Usage

Input:

REGISTER us-west 38 -122 100
REGISTER us-east 41 -74 150
REGISTER eu-west 52 0 200
SET_HEALTHY us-east false
REGISTER us-west 50 -100 50
REGISTER invalid 91 0 100
REGISTER invalid2 0 0 0

Output:

OK
OK
OK
OK
ERROR
ERROR
ERROR

Part 2: Distance Calculation

Implement the Haversine formula to calculate great-circle distances between coordinates.

Requirements

• Calculate great-circle distance using Haversine formula.
• Earth's radius: 6371 km.
• Return distance as integer (round the value).

Pseudocode

To help you, here is the pseudo code for the Haversine formula:

FUNCTION haversine_distance(loc1, loc2):
    CONSTANT earth_radius_km = 6371

    // Convert degrees to radians
    lat1_rad = loc1.latitude * π / 180
    lat2_rad = loc2.latitude * π / 180
    delta_lat = (loc2.latitude - loc1.latitude) * π / 180
    delta_lon = (loc2.longitude - loc1.longitude) * π / 180

    // Haversine formula
    a = sin²(delta_lat / 2)
        + cos(lat1_rad) * cos(lat2_rad)
        * sin²(delta_lon / 2)

    c = 2 * atan2(√a, √(1-a))

    distance = earth_radius_km * c

    RETURN distance
END FUNCTION

Commands to Implement

DISTANCE <lat1> <lon1> <lat2> <lon2>

• Calculates great-circle distance between two coordinates.
• Returns: <distance_km> as integer.
• Always returns a value (no error cases for valid integer coordinates).

Example Usage

Input:

DISTANCE 0 0 0 0
DISTANCE 38 -122 41 -74
DISTANCE 0 0 10 0
DISTANCE 36 140 -33 -71

Output:

0
4080
1112
17167

Part 3: Geographic Routing with Capacity

Implement the core routing algorithm that selects the optimal datacenter based on distance, health, and capacity.

Requirements

• Route to nearest healthy datacenter with available capacity.
• Try datacenters in order of distance (nearest first) until finding one with capacity.
• Return attempted datacenters sorted by distance (only healthy DCs).
• Tie-breaking: if equidistant, sort alphabetically by name.
• Successful route increments datacenter load by 1.
• Datacenter load persists across multiple ROUTE commands.

Commands to Implement

ROUTE <latitude> <longitude>

• Routes to nearest healthy datacenter with available capacity.
• Returns: <selected_dc> <distance_km> <attempted_order>.
• Returns: NONE <attempted_order> if no capacity available.
• attempted_order: Only healthy DCs sorted by distance, comma-separated.
• Increments selected datacenter's load by 1.
• All values are integers.

Example Usage

Input:

REGISTER us-west 38 -122 2
REGISTER us-east 41 -74 100
ROUTE 38 -122
ROUTE 38 -122
ROUTE 38 -122

Output:

OK
OK
us-west 0 us-west,us-east
us-west 0 us-west,us-east
us-east 4080 us-west,us-east

Stripe 需要为全球支付平台实现一个数据中心请求路由系统，按照地理距离、健康状态以及剩余容量为请求选择最合适的数据中心。题目分成三个递进部分：

Part 3 的关键细节：

即使最近的数据中心已满载，仍然要按距离顺序尝试其他健康的数据中心。路由成功后，需要将该数据中心的负载增加 1，并在后续请求中保留这一变化。

此外，attempted_order 要返回按照距离排序的所有健康数据中心名称，而不只是成功选中之前实际检查过的数据中心。这一点可以从第三部分的示例输出看出来。

csoahelp 持续分享北美科技公司及金融机构的真实技术面试题目，提供 Mock Interview 和实时文本辅助服务，帮助候选人更好地理解面试问题、组织技术思路，并清晰表达自己的项目经验。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~