Detect Cycles in Microservice Graph | Dataford Interview Questions

Google Cloud service deployments must start dependencies before the services that rely on them. Given a directed dependency graph, detect whether the graph contains a cycle and return a valid deployment order when it is acyclic.

Formal Specification

Implement order_services(dependencies), where dependencies is a dictionary mapping each service name to a list of services it directly depends on. A service may appear only inside another service's dependency list, and should still be included in the graph.

Return a two-element result (has_cycle, order):

If a cycle exists, return (True, []).
Otherwise, return (False, order), where order contains every service exactly once and each dependency appears before the service that depends on it.
If multiple valid orders exist, return the lexicographically smallest valid order for deterministic deployments.

Constraints

1 <= number of services <= 10^5
0 <= number of dependency edges <= 3 * 10^5
Service names are non-empty strings
Each dependency list contains no duplicate service names
The graph may be disconnected

Function Signature

def order_services(dependencies):

Your question is Detect Cycles in Microservice Graph. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem