Grokking Graph Algorithms for Coding Interviews

0% completed

​

Tasks Scheduling Order (medium)

Problem Statement

There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled.

Given the number of tasks and a list of prerequisite pairs, write a method to find the ordering of tasks we should pick to finish all tasks.

Examples

Example 1:

Input: Tasks=6, Prerequisites=[2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]
Output: [0 1 4 3 2 5] 
Explanation: A possible scheduling of tasks is: [0 1 4 3 2 5]

Example 2:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
Output: [0, 1, 2]

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jonathan

· 4 years ago

I don't think this algorithm is correct, at least it doesn't pass tests when I try it this way and doesn't match Kahn's as I understand it. I think this should be:

graph.get(child).add(parent); // put the parent into it's child's list inDegree.put(parent, inDegree.get(parent) + 1); // increment parent's inDegree

...and likewise on the subsequent problems.

Show 3 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

for

6

[[2,5],[0,5],[0,4],[1,4],[3,2],[1,3]]

I generated [0, 1, 2, 3, 4, 5] I got an error the validator expects the same particular order which is wrong!!

Show 2 replies