Detect Cycles in Trading Dependencies | Dataford Interview Questions

AKUNA CAPITAL models relationships between trading components as a directed dependency graph. An edge A -> B means component A must be processed before component B.

Implement has_cycle(graph) to determine whether the directed graph contains a cycle. A cycle means that no valid processing order exists because at least one component depends, directly or indirectly, on itself.

Formal Specification

Input graph: a dictionary mapping each component name to a list of components it directly depends on.
Every component name is a string. A referenced component may be absent as a key, and should still be treated as a valid node with no outgoing edges.
Output: return True if the graph contains at least one directed cycle; otherwise return False.
The graph may be disconnected and may contain self-loops.

Constraints

1 <= number of distinct components <= 10^5
0 <= number of directed edges <= 2 * 10^5
Component names are non-empty strings
Referenced components may be absent as dictionary keys
Duplicate edges do not affect the result

Function Signature

def has_cycle(graph):

Your question is Detect Cycles in Trading Dependencies. 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