Topological sort, Solving Google Interview Question

If we want to become a full-stack developer we follow the following path :

First, we learn basic HTML & CSS, then we learn Javascript. Then the path diverges into FrontEnd development and BackEnd development, for becoming a backend developer we need to study a database and finally we become a full stack developer.

So this path is fixed, to learn a frontend framework, you need to know the basics of HTML, CSS, and JavaScript.

There is a one-directional relationship between components, we can't first learn React and then learn HTML.

Topolocial Sort is the ordering in which things should happen/occur, there are many real-life use like when processing large data, data is supplied in chucks so that the resource utilization is optimal and then the processed data is transferred. Largest friendship distance in the network also known as six degrees of separation on a social media network is solve using Topological Sort.

Now that we know what's topological sort and it's uses, let's solve a question asked frequently at Google.

X-----------------------------------------------------------X

Question: Course Scheduler

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

Given input is numCourses for the number of courses to take, prerequisites array which determines the dependency between courses. If it's not possible then return 0.

For eg : if give data is [[2,0],[2,1],[3,2],[4,2],[4,5],[6,3],[6,4]]

Our graph will look like :

From this we can say a possible order could be : [0,1,5,2,3,4,6]

Step 1: Building the graph

Graphs are represented as adjacency list/adjacency matrix. Both are easy to implement. In this case, we shall use the adjacency list since the graph is a sparse graph (ie many nodes aren't connected to each other).

Along with our graph, we shall maintain an array, indegree which will maintain the count of prerequisites for node "i"

     var topologyOrder = function(numCourses,prerequisites){

        // create each individual node
        let graph = new Array(numCourses+1);

        // to track the number of dependencies required by each node
        let indegree = new Array(numCourses+1).fill(0);

        for(let i=0;i<numCourses+1;i++){
            graph[i] = []; 
        }

        for(let prerequisite of prerequisites){
            let from = prerequisite[1];
            let to = prerequisite[0];
            graph[from].push(to);
            indegree[to]++;
        }
        console.log(graph);
        console.log(indegree);
  }

By end of this operation our graph will look like :

   graph = [[2]                // 0 -> 2
            [2]                // 1 -> 2
            [3,4]              // 2 -> 3, 2 -> 4
            [6]                // 3 -> 6
            [6]                // 4 -> 6
            [4]                // 5 -> 4
            []]                // 6 -> end   

 indegree = [ 0,               // 0 ie no prerequisites
              0,             
              2,               // 2 courses are required before this
              1,               // 1 course is required
              2,               
              0,
              2 ]

Now that we have a graph, information about how many courses needs to be finished before taking a certain course. Let's move ahead to the next step.

Breadth First Travesal

First step will be to take classes which have indegree of "0" ie no prerequisites.

Also, we maintain a queue to process each node in graph as we always do in a BFS traversal.

   let queue = [];

   for(let i=0;i<indegree.length;i++){
       if(indegree[i] == 0){
            queue.push(i);
       }
   }

Our next step will be to process each node in queue, but before that, we need to ensure that there are nodes to be processed in the queue.

Eg: if given input is [[0,1],[1,0]], ie 0 -> 1 and 1 -> 0. We're in a deadlock.

   if(queue.length == 0) return 0;

Our next question is how to process the nodes? And at the same time, we have to ensure that there's a unidirectional flow and a node isn't visited again because then we end up in an infinite loop.

So we create an array and a set and a counter :

   let res = [];                // to store the result
   let visited = new Set();     // to store visited nodes
   let count = 0;               // safety check to ensure all nodes are visited

Next steps are :
Step 1> Go through the queue,
Step 2> Pop a node
Step 3> Process that node by setting it as visited and adding it to result
Step 4> visit all the child nodes of current node and decrease their indegree by 1
Step 5> Increment the count
Step 6> repeat steps 1 - 5 till queue is empty.

while(queue.length>0){
      // pop a node from queue
      let node = queue.shift();

      // check if it's visited, if it's the return 0
      if(visited.has(node)) return 0;

      // add node to visited set
      visited.push(node);

      // add node to result
      res.push(node);

      //loop over all the nodes require current node as a prerequisite
      for(let n of graph[node]){

          // since current node is processed, decrease the indegree of node "n" by 1
          indegree[n]--;

          // if node "n" indegree equals 0, add it to the queue so that it can be processed
         if(indegree[n] == 0) queue.push(n);
      }

      // incremenet count by 1
      count++;
}

Let's see the above steps in animation. If possible open the gif in another tab and compare each step with the above code.

putting it all together :

 var topologyOrder = function(numCourses,prerequisites){

       let graph = new Array(numCourses);

       let indegree = new Array(numCourses);

       for(let i=0;i<numCourses;i++){
           graph[i] = []; 
       }

       for(let prerequisite of prerequisites){
           let from = prerequisite[1];
           let to = prerequisite[0];
           graph[from].push(to);
           indegree[to]++;
       }

       let queue = [];

       for(let i=0;i<indegree.length;i++){
            if(indegree[i] == 0){
               queue.push(i);
            }
       }

       if(queue.length == 0) return 0;

       let res = [];                
       let visited = new Set();     
       let count = 0;

       while(queue.length>0){
             let node = queue.shift();
             if(visited.has(node)) return 0;
             visited.add(node);
             res.push(node);
             for(let n of graph[node]){
                  indegree[n]--;
                  if(indegree[n] == 0) queue.push(n);
             }
             count++;
      }

      return count == numCourses ? res : 0;
}

Thanks a lot if you made it till here :) I hope you liked my article.

If I messed up somewhere or didn't explain clearly, do comment.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Algorithm/TopologicalSort.js

Comments

[Lee Wilson]

Small issue: graph[from].add(to); should be .push (to) instead.

but also i am not getting same output as you for that portion of the function, can you specify the parameters you are calling with?
my graph variable shows
[ [ 2, 1 ], [], [ 3, 4 ], [ 6 ], [ 5, 6 ], [], [] ]

[Akhil]

Omg thanks for pointing out, the graph is of another problem I am working on and I miss-matched it.

Graph is :[[2,0],[2,1],[3,2],[4,2],[4,5],[6,3],[6,4]]

I have updated the code :).

Thanks again for pointing out my mistake.

[Andrew]

Thanks for publishing this, and maintaining it.

I think the e.g input in the article has a mistake:

[5,4], should be [4,5],

[Akhil]

Thanks for reading the article :), and updated my mistake.

[Arun J]

Hi,
Above the second diagram, it is still not corrected

For eg : if give data is [[2,0],[2,1],[3,2],[4,2],[5,4],[6,3],[6,4]]

[petelomax]

I cannot see where you corrected that but it is still wrong just above step 1.

[Arun J]

For eg : if give data is [2,0],[2,1],[3,2],[4,2],[5,4],[6,3...

[Médéric Burlet]

Nice explanation however i'd like to correct the following:

If we want to become a full-stack developer we follow the following path :

Being full-stack does not mean learning javascript. There are many ways to be full-stack; from .NET to PHP to Ruby to Python.

I would correct to:

If we want to become a full-stack developer we can follow the following path for javascript :

[Akhil]

Noted :)

[Dong Nguyen]

Thank you for your article. You explained as well, however your implementation may have some problems. I didn't run your code but I guess that it will not be able to work as expected. For example:

• line 20 and line 37, the keyword int

for(int i=0;i<indegree.length;i++){

• line 35, visited is Set, not Array, so you have to use add(), not push()

visited.push(node);

Please check and fix them :)

[Akhil]

Omg, thanks for pointing out! Code updated :)