Topological Sort Interview Questions & Tips

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 = ["ab","a","b"] Output: ""

Our solution article goes in-depth on the graph generation step as well as the solution. The above example ends up being represented as follows:

With this handy, you can leverage standard BFS to generate the final order:

["k"]→ ["d", "a"], ["c"]

Leaving us with the solution:

"kdac"

When to Use Topological Sort in Interviews

In an interview, there are some simple heuristics you can follow to identify topological sort problems: If any of these ring true, topological sort would be a viable candidate solution to your problem.

1. Is the problem related to dependencies between objects?
2. Is the problem related to scheduling or ordering tasks?
3. Is the problem related to finding a linear order of elements based on certain rules or conditions?

If the problem involves organizing objects or tasks based on some conditions or rules, there is a good chance that topological sort can be used to solve the problem.

Common Mistakes in Interviews Featuring Topological Sort

Graph Building

This is by far the most critical step in the algorithm and one where candidates struggle the most. While this is an opinion thus take it with a grain of salt, using an adjacency list tends to be the easiest way to implement the graph. That should address the structural representation. Our graphs article provides more alternatives that you can look into.

Keep an eye out for Vertices without relationships, and make sure they are incorporated into the graph.

Failing to Incorporate Isolated Vertices

Speaking of isolated vertices, some of the letters can sometimes have no apparent relationships. Consider the following example:

["baa", "abcd", "abca", "cab", "cad", “e”]

The graph representation of these would be:

{ "a": ["b", "d"], "b": ["c"], "c": [], "d": [], "e": []}

Note that there is an isolated node, e. This node does not have any edges going in or out. No words depend on it. In the Tom and Dog example, this would be the equivalent of saying:

“Tom is in a car in a parking lot in the basement of a skyscraper with their dog in the backseat and there is a Cat at Home”

In this regard, the Cat and Home have nothing to do with the rest of the setting. When generating the order, they can be incorporated at the end or at the start. In our case, e would be at the end. In fact, this tends to generalize quite well. Any time you have isolated vertices, the simplest way to handle them is to inject them at the end of your output list.

Failing to Generate All Possible Orderings

In an interview, make sure to clarify with your interviewer if they want one solution or all possible solutions. As you’ve seen, the same graph can be ordered in different ways. The reason why BFS is what we recommend when doing traversals is that it generates all possible orders out of the box. That said, the algorithm will usually use extra space, so clarifying the problem requirements is key. If you only need to come up with one solution, DFS would work. Be mindful of the isolated node problem in this regard.

Failure to Identify When There is No Solution

To keep it simple, if a cycle is detected, there is no possible ordering. Example 3 illustrates this perfectly:

Input: [“ab, “a”, “b”] Graph Representation: { "a": "b", "b": "a"}

This is a chicken and egg problem. Which one came first if the egg comes from the chicken and the chicken from the egg? Well, obviously, the answer here is 42!

Failing to Mark Visited Vertices

Once you add a node, it is key to mark it as visited in the graph to avoid visiting it more than once. This is an implementation pitfall and our DFS and BFS article go in-depth on how to handle this.

What to Say in Interviews to Show Mastery Over Topological Sort

Topological sort is one of the few medium-to-hard algorithms that are very common in interviews. Frankly speaking, if you are able to implement it and avoid the pitfalls above, that ought to be enough to showcase mastery. A couple of things to keep in mind:

Graph Representation

Use the simplest, viable graph structure. Do not reinvent the wheel here. Hint: Use an adjacency list if possible. It will make your life much easier! While doable, implementing the graph following a Node structure would be borderline overkill. Our graph article has an entire section dedicated to this!

Exhaustive Clarification Questions to Ask Your Interviewer

Please don't skip this step in your interview! Two key questions you should always ask:

1. Do we need all possible orders?
2. How do we deal with isolated nodes? (Quick tip on this, always propose to append them at the end as an edge case as this will work in most cases and helps separate out processing logic which can keep your implementation clean)

Common Topological Sort interview Questions

Adjacent Topics to Topological Sort

About the Author