What is topological sort and when is it used? | Interview Question

Q: What is topological sort and when is it used?

**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 Think about getting dressed in the morning. Socks go on before shoes. Underwear goes on before trousers. Trousers go on before shoes and before the belt. A shirt goes on before a tie. Nobody writes this down, but there are rules: **some things must happen before other things**. Some pairs have no rule at all — you can put on your watch whenever you like. Now imagine a computer has to do the same thing for 50,000 jobs: compile these files before linking that program, install this package before that

The problem

Question presented to candidate: "What is a topological sort, and when would you use one? Walk me through an algorithm for it and code it in Python."

What a strong answer should cover:

A topological order lists every node so that each edge u -> v has u before v; it exists only for a DAG (no cycles), and it is usually not unique.
Kahn's algorithm: in-degrees, a queue of in-degree-0 nodes, decrement neighbours; fewer than n nodes placed means a cycle.
The DFS alternative: reverse post-order, with three colours to catch a back edge.
O(V + E) time and space for both, and real uses: build order, package installs, spreadsheets, course prerequisites, DP on a DAG.
Python specifics: collections.deque for an O(1) popleft (not list.pop(0)), heapq (a min-heap) for the smallest order, the 1000-frame default recursion limit for DFS, and the standard-library graphlib.TopologicalSorter.

Code / implementation expected: Yes — a kahn(n, edges) function in Python that returns an order or signals a cycle.

graphs
topological-sort

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

Think about getting dressed in the morning. Socks go on before shoes. Underwear goes on before trousers. Trousers go on before shoes and before the belt. A shirt goes on before a tie. Nobody writes this down, but there are rules: some things must happen before other things. Some pairs have no rule at all — you can put on your watch whenever you like.

Now imagine a computer has to do the same thin

The solution is hidden so you can try first

13 min read · 12 sections

Python code

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

PythonKahn's algorithm on a build graph, then with a cycle

Practice

PythonThe queue picks the order: FIFO vs min-heap, and all 13 orders

Practice

PythonDFS reverse post-order on the same build graph

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.