Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: All Tasks Scheduling Orders
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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 print all possible ordering of tasks meeting all prerequisites.

Examples

Example 1:

Input: Tasks=4, Prerequisites=[3, 2], [3, 0], [2, 0], [2, 1]
Output: 
1) [3, 2, 0, 1]
2) [3, 2, 1, 0]
Explanation: There are two possible orderings of the tasks meeting all prerequisites.

Example 2:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
Output: [0, 1, 2]
Explanation: There is only possible ordering of the tasks.

Example 3:

Input: Tasks=6, Prerequisites=[2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]
Output: 
1) [0, 1, 4, 3, 2, 5]
2) [0, 1, 3, 4, 2, 5]
3) [0, 1, 3, 2, 4, 5]
4) [0, 1, 3, 2, 5, 4]
5) [1, 0, 3, 4, 2, 5]
6) [1, 0, 3, 2, 4, 5]
7) [1, 0, 3, 2, 5, 4]
8) [1, 0, 4, 3, 2, 5]
9) [1, 3, 0, 2, 4, 5]
10) [1, 3, 0, 2, 5, 4]
11) [1, 3, 0, 4, 2, 5]
12) [1, 3, 2, 0, 5, 4]
13) [1, 3, 2, 0, 4, 5]

Solution

This problem is similar to Tasks Scheduling Order, the only difference is that we need to find all the topological orderings of the tasks.

At any stage, if we have more than one source available and since we can choose any source, therefore, in this case, we will have multiple orderings of the tasks. We can use a recursive approach with Backtracking to consider all sources at any step.

Step-by-step Algorithm

  1. Initialize the Graph:

    • Create a HashMap inDegree to count the incoming edges for every vertex.
    • Create a HashMap graph to represent the adjacency list of the graph.
    • Initialize the orders list to store all possible orders.

  2. Build the Graph:

    • For each task, set the initial in-degree to 0 and create an empty adjacency list.
    • For each prerequisite pair [parent, child]:
      • Add child to the adjacency list of parent.
      • Increment the in-degree of child by 1.

  3. Find All Sources:

    • Initialize a queue sources and add all vertices with 0 in-degrees.

  4. Print All Topological Sorts:

    • Use a recursive function to explore all possible topological sorts.
    • For each source:
      • Add the source to the sortedOrder list.
      • Remove the source from the queue.
      • Decrement the in-degrees of its children.
      • If a child's in-degree becomes 0, add it to the queue.
      • Recursively call the function with the updated queue and sorted order.
      • Backtrack by removing the source from the sorted order and restoring the in-degrees of its children.

  5. Check for Cycles:

    • If the sortedOrder list contains all tasks, add it to the orders list.

Algorithm Walkthrough

Let's walk through the algorithm using the input Tasks=4, Prerequisites=[3, 2], [3, 0], [2, 0], [2, 1].

  1. Initialization:

    • inDegree = {0: 0, 1: 0, 2: 0, 3: 0}
    • graph = {0: [], 1: [], 2: [], 3: []}

  2. Build the Graph:

    • Add edges and update in-degrees:
      • Add edge 3 -> 2: inDegree = {0: 0, 1: 0, 2: 1, 3: 0}, graph = {0: [], 1: [], 2: [], 3: [2]}
      • Add edge 3 -> 0: inDegree = {0: 1, 1: 0, 2: 1, 3: 0}, graph = {0: [], 1: [], 2: [], 3: [2, 0]}
      • Add edge 2 -> 0: inDegree = {0: 2, 1: 0, 2: 1, 3: 0}, graph = {0: [], 1: [], 2: [0], 3: [2, 0]}
      • Add edge 2 -> 1: inDegree = {0: 2, 1: 1, 2: 1, 3: 0}, graph = {0: [], 1: [], 2: [0, 1], 3: [2, 0]}

  3. Find All Sources:

    • Sources with 0 in-degrees: sources = [3]

  4. Process each nodes:

    1. Recursive Call with Source 3:

    • Add 3 to sortedOrder: sortedOrder = [3]

    • Remove 3 from sources: sources = []

    • Decrement in-degrees of children of 3:

      • inDegree = {0: 2, 1: 1, 2: 0, 3: 0}

    • Add new source 2 to sources: sources = [2]

    1. Recursive Call with Source 2:

    • Add 2 to sortedOrder: sortedOrder = [3, 2]

    • Remove 2 from sources: sources = []

    • Decrement in-degrees of children of 2:

      • inDegree = {0: 1, 1: 0, 2: 0, 3: 0}

    • Add new sources 0 and 1 to sources: sources = [0, 1]

    1. Recursive Call with Source 0:

    • Add 0 to sortedOrder: sortedOrder = [3, 2, 0]

    • Remove 0 from sources: sources = [1]

    • Decrement in-degrees of children of 0 (none)

    1. Recursive Call with Source 1:

    • Add 1 to sortedOrder: sortedOrder = [3, 2, 0, 1]

    • Remove 1 from sources: sources = []

    • Decrement in-degrees of children of 1 (none)

    • sortedOrder contains all tasks: add [3, 2, 0, 1] to orders

    1. Backtrack from Source 1:

    • Remove 1 from sortedOrder: sortedOrder = [3, 2, 0]

    • Restore in-degrees: inDegree = {0: 1, 1: 0, 2: 0, 3: 0}

    1. Backtrack from Source 0:

    • Remove 0 from sortedOrder: sortedOrder = [3, 2]

    • Restore in-degrees: inDegree = {0: 2, 1: 0, 2: 0, 3: 0}

    • Add source 0 back to sources: sources = [0, 1]

    1. Recursive Call with Source 1:

    • Add 1 to sortedOrder: sortedOrder = [3, 2, 1]

    • Remove 1 from sources: sources = [0]

    • Decrement in-degrees of children of 1 (none)

    1. Recursive Call with Source 0:

    • Add 0 to sortedOrder: sortedOrder = [3, 2, 1, 0]

    • Remove 0 from sources: sources = []

    • Decrement in-degrees of children of 0 (none)

    • sortedOrder contains all tasks: add [3, 2, 1, 0] to orders

    1. Backtrack from Source 0:

    • Remove 0 from sortedOrder: sortedOrder = [3, 2, 1]

    • Restore in-degrees: inDegree = {0: 1, 1: 0, 2: 0, 3: 0}

    1. Backtrack from Source 1:

    • Remove 1 from sortedOrder: sortedOrder = [3, 2]

    • Restore in-degrees: inDegree = {0: 2, 1: 0, 2: 0, 3: 0}

    • Add source 1 back to sources: sources = [0, 1]

    1. Backtrack from Source 2:

    • Remove 2 from sortedOrder: sortedOrder = [3]

    • Restore in-degrees: inDegree = {0: 2, 1: 1, 2: 1, 3: 0}

    • Add source 2 back to sources: sources = [2]

    1. Backtrack from Source 3:

    • Remove 3 from sortedOrder: sortedOrder = []

    • Restore in-degrees: inDegree = {0: 2, 1: 1, 2: 1, 3: 0}

    • Add source 3 back to sources: sources = [3]

    1. Final Orders:
    • [3, 2, 0, 1]
    • [3, 2, 1, 0]

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Time and Space Complexity

If we don’t have any prerequisites, all combinations of the tasks can represent a topological ordering. As we know, that there can be N! combinations for ‘N’ numbers, therefore the time and space complexity of our algorithm will be O(V! * E) where ‘V’ is the total number of tasks and ‘E’ is the total prerequisites. We need the ‘E’ part because in each recursive call, at max, we remove (and add back) all the edges.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible