Mid-levelMid (3–6 yrs)PythonAmazonGoogleLinkedIn
Topological sort cycle
How does Kahn’s algorithm detect a cycle while doing topological sort? Give complexity.
Answers use simple, clear English.
Quick interview answer
Build indegree + adjacency. Queue all zero-indegree nodes; repeatedly reduce neighbors’ indegrees. If processed count < V, a cycle remains (nodes never reached zero indegree).
Detailed answer
Build indegree + adjacency. Queue all zero-indegree nodes; repeatedly reduce neighbors’ indegrees. If processed count < V, a cycle remains (nodes never reached zero indegree). Time O(V+E), space O(V+E).
Real example & use case
Course schedule: return empty order if prerequisites cycle.
Pros & cons
Pros: detects cycle + order together. Cons: only DAGs yield full order.
#dsa#graph#topo-sort