Reason About Dependency Loading with Topological Sort

Module Dependency Resolver

Robinhood's trading platform relies on dozens of internal micro-services and libraries (such as market_data, order_routing, risk_engine, and auth). When starting up an environment, services must be initialized in an order such that every dependency of a service is fully loaded before the service itself starts.

You are given a list of service names services and a list of dependency pairs dependencies, where each pair [u, v] indicates that service v depends on service u (i.e., u must be loaded before v).

Write a function to return a valid sequence in which all services can be loaded.

Requirements

1. If there are circular dependencies (a cycle), return an empty list [] to indicate that the system cannot be safely loaded.
2. If multiple valid initialization orders exist, return the order that is lexicographically smallest at each step (tie-breaking).
3. Any service mentioned in services must appear in the final output unless there is a cycle.

Function Signature

def resolve_load_order(services: list[str], dependencies: list[list[str]]) -> list[str]:
    pass

Examples

Example 1:

services = ["auth", "risk_engine", "order_routing", "market_data"]
dependencies = [
    ["auth", "risk_engine"],
    ["auth", "order_routing"],
    ["market_data", "order_routing"],
    ["risk_engine", "order_routing"]
]
# Output: ["auth", "market_data", "risk_engine", "order_routing"]

Explanation: Both auth and market_data have no prerequisites. Because auth is lexicographically smaller than market_data, it is chosen first. Then market_data is selected. Next, risk_engine (depends only on auth) becomes available, followed by order_routing.

Example 2:

services = ["service_a", "service_b"]
dependencies = [
    ["service_a", "service_b"],
    ["service_b", "service_a"]
]
# Output: []

Explanation: service_a and service_b depend on each other, creating a circular dependency.

Constraints

• 1 <= len(services) <= 1000
• 0 <= len(dependencies) <= 5000
• Each service name consists of lowercase English letters and underscores, with length between 1 and 30.
• All names in dependencies are guaranteed to exist in services.
• Dependencies may contain duplicate edges.