Topological Sort with Cyclic Dependency Handling
viaGlassdoor
Problem: Given a directed graph representing dependencies, produce a topological ordering of the nodes, and correctly detect and handle cyclic dependencies (where no valid topological order exists).
Approach: Use Kahn's algorithm (BFS with in-degree counting) -- repeatedly remove nodes with in-degree 0, appending them to the order and decrementing neighbors' in-degrees. If not all nodes are processed by the end, a cycle exists. Alternatively, use DFS with a recursion-stack/visiting-state marker to detect back-edges (cycles) while building the order via a stack on finish times.
asked …