Frontend School

Task Dependency Resolver

DSA
easy

Task Dependency Resolver

Easy
Graph
Topological Sort
Dependencies

Overview

In many real-world scenarios, tasks have dependencies. For instance, in software build systems, certain modules must be compiled before others. In project management, some activities can only begin after their prerequisites are met. Ensuring tasks are executed in a valid order is crucial to prevent deadlocks and ensure successful completion.

What you need to do / Task

You are given a total number of tasks and a list of prerequisite pairs. Each task is labeled from 0 to numTasks - 1. A prerequisite pair [task, prerequisite] indicates that task cannot be started until prerequisite has been completed.

Your goal is to find one valid order in which all tasks can be completed. If it's impossible to complete all tasks due to a circular dependency (a cycle), you should indicate this.

Input & output

findTaskOrder(numTasks: number, prerequisites: number[][]): number[]

  • numTasks: An integer representing the total number of tasks, labeled from 0 to numTasks - 1.
  • prerequisites: An array of arrays, where each inner array [task, prerequisite] signifies that task depends on prerequisite. That is, prerequisite must be completed before task can begin.
  • Returns: An array of integers representing a valid topological order of tasks. If no such order exists (i.e., there's a cycle in the dependencies), return an empty array [].

Clarifications

  • Tasks are always represented by non-negative integers from 0 to numTasks - 1.
  • If numTasks is 0, an empty array [] should be returned as there are no tasks.
  • If prerequisites is an empty array, all tasks can be completed in any order (e.g., [0, 1, ..., numTasks - 1]). Your algorithm should produce one such valid order.
  • If multiple valid orders exist, any one of them is acceptable.

Examples

1

Example 1

Input:

numTasks = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]

Output:

[0,1,2,3]

Note:

Task 0 has no prerequisites. Tasks 1 and 2 depend on 0. Task 3 depends on both 1 and 2. A valid order is to complete 0 first, then 1 and 2 (in any order), and finally 3.

2

Example 2

Input:

numTasks = 2, prerequisites = [[1,0], [0,1]]

Output:

[]

Note:

Task 1 depends on 0, and Task 0 depends on 1. This forms a circular dependency, making it impossible to complete both tasks. Thus, an empty array is returned.

3

Example 3

Input:

numTasks = 3, prerequisites = []

Output:

[0,1,2]

Note:

With no prerequisites, all tasks can be completed in any order. The solution might return them in numerical order or another valid permutation.

Constraints

Constraints & assumptions

  • 0 <= numTasks <= 2000
  • 0 <= prerequisites.length <= numTasks * (numTasks - 1)
  • Each prerequisites[i] has length == 2.
  • 0 <= prerequisites[i][0], prerequisites[i][1] < numTasks
  • All prerequisite pairs [task, prerequisite] are unique.
  • No self-loops are present (e.g., [0,0] will not be in prerequisites).

What interviewers evaluate

  • Correctness: Does the solution correctly identify a valid task order and detect cycles?
  • Algorithm Choice: Is an appropriate and efficient algorithm (e.g., Kahn's algorithm or DFS-based topological sort) used?
  • Graph Representation: Is the underlying graph structure represented efficiently for the given constraints?
  • Edge Case Handling: Does the code gracefully handle scenarios such as zero tasks, no prerequisites, or the presence of cycles?
  • Code Quality: Is the code clean, readable, and well-structured, demonstrating good software engineering practices?

Loading editor...