Cycle Detection in Service Graph | Dataford Interview Questions

Tencent Cloud TKE services may depend on other services during deployment. Given a directed dependency graph, determine whether any circular dependency exists.

A directed edge A -> B means service A depends on service B. Return true if the graph contains a directed cycle, otherwise return false.

Formal Specification

Implement has_cycle(dependencies), where dependencies is a dictionary mapping each service name to a list of services it directly depends on. Service names are non-empty strings. A dependency may reference a service that does not appear as a dictionary key, and such a service should be treated as having no outgoing edges.

The graph can be disconnected. Self-dependencies count as cycles.

Constraints

1 <= number of listed services <= 10^5
0 <= number of dependency edges <= 2 * 10^5
Service names are non-empty strings of length at most 100
Referenced services may be absent as dictionary keys
The graph may contain disconnected components

Function Signature

def has_cycle(dependencies):

Your question is Cycle Detection in Service 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