[Guide] How to identify and solve topological sort questions
Shreya
2835
Topological SortGoogleInterview

Topological Sort - A compilation of topological sort interview questions

  • using dfs: use stack
  • using bfs: kahns algorithm, can be used to detect cycle too

How to identify topological sort questions?
Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering.

  • Problems involving dependencies (e.g., course prerequisites, task scheduling).
  • Problems where the input is described as a directed graph, and you need to find:
  • The order in which tasks or nodes should be processed/appear.
  • If it's possible to complete all tasks (cycle detection in a DAG).

Examples of good topological sort questions:

  1. Course Schedule
  2. Problems involving dependencies (e.g., course prerequisites, task scheduling).
    Problems where the input is described as a directed graph, and you need to find:
    The order in which tasks or nodes should be processed.
    If it's possible to complete all tasks (cycle detection in a DAG).
  3. in a classroom, a number was written on the blackboard and students were supposed to see the number once and then turn around. Students remembered some part of number ( for example if the number was 123457 some remembered 123 another remembered 37..) so basically you are given a list of guesses by the students and you have to return the correct number.
  4. Printing all topological sorts
    Question:Given a binary tree, if a node is leaf node, we can remove it, the remove order could be different. Write a function to print one removal order.
Example:   
				 1
               /    \
			 2       3
		  /    
		4

possible remove order: 
[4, 2, 3, 1]
[4, 3, 2, 1]
[3, 4, 2, 1]

Return one of the possible solution.
This first question is simple, just post-order traversal.
However, let's see what is next.
Follow up:


Write a function to print all the possible solutions.
Example:   
				 1
               /    `\`
			 2       3
		  /   ` \`
		4       5

Return:
[
	[3, 4, 5, 2, 1],
	[3, 5, 4, 2, 1],
	[4, 5, 2, 3, 1],
	[4, 5, 3, 2, 1],
	[4, 3, 5, 2, 1],
	[5, 3, 4, 2, 1],
	[5, 4, 3, 2, 1],
	[5, 4, 2, 3, 1]
]

All topological sorts: code link ⭐⭐⭐⭐⭐

  1. Given list of objects-
    {a, b, "right"} --> a is to the right of b
    {c,b, "right"} --> c is to the right of b
    {b,a, "left"} --> b is to the left of a
    sort them based on left and right conditions.
    output any valid output.
    one valid output is - b, a, c

 inequalities=[ ("a","<","b"),("b",">","c"),("a","<","c"),("d",">","b")]
Given a list of inequalities does it hold true/false?
o/p=
[ ("a","<","b"),("b","<","a") ] False
[ ("d",">","a")] True

  1. You want to run two tests on a device. Each test has a series of setup tests that must be done in order.
    For example,
    you need to complete Step A, B, and C in that order to run test1.
    Then there is test2, which needs steps X, B, and Z to be setup in that order to run.
    You could setup the device by doing the steps like this A, B, C, X, B Z. But that would be inefficient because you are doing step B twice. How would you make the list of steps such that there are no duplicate steps but the order of the steps is maintained. For example, in this case, the optimized correct steps are A, X, B, C,Z.

  2. Parallel Courses
    The problem presents a scenario where you have n courses numbered from 1 to n. You are also given a list of pairs, relations, representing the prerequisite relationships between the courses. Each pair [prevCourse, nextCourse] indicates that prevCourse must be completed before nextCourse can be taken.
    The goal is to determine the minimum number of semesters required to complete all n courses, given that you can take any number of courses in a single semester, but you must have completed their prerequisites in the previous semester. If it's not possible to complete all courses due to a circular dependency or any other reason, the result should be -1.

  3. Suppose we are creating a string replacement library. Given a map of string replacements, replace the value in the input string

Given map {X=>123, Y=456}
Input: %X%_%Y%
Output: 123_456
Given map {USER=>admin, HOME=>/%USER%/home}
Input: I am %USER% My home is %HOME%
Output: I am admin My home is /admin/home

Basic topological sorting template

Comments (3)