Course Schedule: detect cycle with topological sort (Kahn vs DFS)?

Q: Course Schedule: detect cycle with topological sort (Kahn vs DFS)?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Two friends are asked to plan a pile of chores where some chores must come before others ("buy paint before painting", "move the sofa before painting", "paint before hanging pictures"). **Friend K** looks at the list and asks: *"What can I do right now, with nothing blocking it?"* She does those, crosses them off, and asks the question again. When nothing is left that she can start, either she is done or some chores are blocking each other in a loop. **Friend D** picks a chore and asks: *"What doe

The problem

Question presented to candidate: "For Course Schedule you can detect the cycle with Kahn's algorithm or with DFS. Explain both, tell me how each one spots a cycle, and when you would choose one over the other. Show me both in Python."

What a strong answer should cover:

Kahn: in-degrees plus a queue; a cycle exists when fewer than V nodes get placed, and the leftover nodes are the cycle plus everything downstream of it.
DFS: WHITE/GRAY/BLACK colours; an edge into a GRAY node (a back edge) is a cycle, and the GRAY path gives the exact cycle; reverse finish order is the topological order.
Both are O(V + E) time and O(V + E) space; they usually produce different valid orders.
Trade-offs: Kahn has no recursion and gives levels and easy lexicographic order; DFS stops at the first cycle and can print it, but needs an explicit stack on deep graphs.
Python specifics: recursive DFS hits the default 1000-frame recursion limit (RecursionError), so an explicit stack (a list of [node, index] frames) or Kahn with collections.deque is the robust choice.

Code / implementation expected: Yes — both a Kahn function and a three-colour DFS function in Python, ideally with the DFS able to return the cycle.

topo
graph
Amazon

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Two friends are asked to plan a pile of chores where some chores must come before others ("buy paint before painting", "move the sofa before painting", "paint before hanging pictures").

Friend K looks at the list and asks: "What can I do right now, with nothing blocking it?" She does those, crosses them off, and asks the question again. When nothing is left that she can start, either she is don

The solution is hidden so you can try first

12 min read · 9 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonKahn and DFS side by side: orders, stuck sets and the actual cycle

Practice

PythonA 200,000-node chain: Kahn and explicit-stack DFS, no recursion

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.