Topological Sort Interview Questions & Tips

By Githire B. Wahome | Last updated: July 24, 2023

What Is Topological Sort?

Topological sort is an algorithm used in graph theory to sort a directed acyclic graph (DAG) based on relationships between the vertices. It arranges the vertices of a DAG in a linear order such that for each directed edge (u, v), vertex u comes before vertex v in the ordering. This algorithm is commonly used in tasks that require a specific order of execution, such as scheduling jobs or tasks.

In a DAG, there are no cycles, which means that there is no way to start at a vertex and reach itself by following its edges. This property is important because it makes it possible to order the vertices in a way that respects the direction of the edges.

Topological sort can be performed using both depth-first search (DFS) and Breadth First Search (BFS) algorithms. My preference tends to be BFS as some objects tend to be on the same level and BFS makes it easy to incorporate these while generating the sorted output on the fly. It also handles isolated vertices out of the box.

Topological sort has many real-world applications, including task scheduling, project management, and software engineering. In the context of interviews, it is the go-to solution for problems such as course scheduling and good old Alien Dictionary. A collection of topological sort problems and solutions can be found here

Companies That Ask Topological Sort Questions

How to Perform Topological Sort

Often, an introduction to topological sort focuses on graph properties, which can make it a bit hard to understand. This is why most of the questions related to the topic are tagged Hard. As such, let us try and approach it like an alien who has no clue what even the word topology means!

What Exactly Is 'Topology'?

According to the Oxford Dictionary:

[Noun]

The way in which constituent parts are interrelated or arranged.

Example usage in a sentence: "using distances determined in this manner ignores existing road conditions and topology that can potentially affect travel time and costs"

Here's a common definition from the field of mathematics.

The study of geometric properties and spatial relations unaffected by the continuous change of shape or size of figures.

Hmm, not particularly helpful, is it? Perhaps we can turn to Geography as that is where the term is most commonly encountered;

Geographic topology is a branch of geography that studies the spatial relationships between objects or features on the earth's surface. It is concerned with understanding how these objects or features are connected and how they relate to one another in space.

Much better. In essence, topology entails defining how objects in space are interconnected. The brain is in the head, Food is on the table, A car is in a parking lot, or Leetcode should go to hell. Okay, maybe not that last one, but the idea here is that we have objects that have a relationship where objects are connected through relationships such as contains, on top of, is in.

Given the relationships, there exists an innate order to the objects. You cannot access the brain without first getting through the head, food ‘on’ a plate cannot be accessed from below, and of course, you cannot master leetcode algorithmic questions without going through hell! (I'm sorry, it was too perfect not to mention!)

If we have multiple objects chained together, the relationships form a graph. Take this sentence:

“Tom is in a car in a parking lot in the basement of a skyscraper with their dog in the backseat.”

Can you see how a graph can define the relationships in this?

In this example, the sentence is broken down into its constituent objects which represent the vertices of the graph, The edges represent an ordered relationship in space. So the Skyscraper contains a basement which contains a Parking lot that has Tom and the Car on it. The car has a Backseat which has a Dog on it.

With this in mind, we can sort the vertices as follows starting from the object that contains everything to the most stand-alone one:

[Skyscraper, Basement, Parking lot, Tom, Car, Backseat, Dog]

The key takeaway here is that order can exist between non-numerical or alphabetical objects. In fact, you can argue that topological sort is a superset to all sort operations since numerals, as well as letters, can be thought of as objects in Euclidean and Alphabetical space respectively thus they maintain an inherent topological ordering.

1. To generalize this discussion, most interview problems related to topological sorting entail a two-step challenge:
2. Generating the graph: See our graph article for various ways to implement graphs. Traversing the graph to generate the topological order.

Your task as a candidate is to make it clear what the objects are and how they are related, and then to implement a traversal algorithm that outputs the vertices in order. Take the Alien Dictionary problem for example;

The Alien Dictionary problem involves determining whether a given order of words is valid according to an imaginary dictionary, and if so, returning a possible order for the letters used. The challenge of this problem is both in understanding how to approach the task logically, as well as in applying graph traversal algorithms to devise a solution.

Example 1 Input: words = ["kaa","akcd","akca","cak","cad"] Output: "kdac"

Example 2 Input: words = ["b","a"] Output: "ba"

Example 3 Input: words = `[\