Katkat
Back

Compute minimal time to finish dependent tasks

UberMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of graph algorithms and scheduling, specifically reasoning about task dependencies, parallel execution, and cycle detection in directed graphs.

Coding: Task Scheduling With Prerequisites (Parallel Allowed)

You have n tasks labeled 1..n. Each task takes exactly 1 unit of time to complete. Some tasks have prerequisites.

You are given a list of prerequisite pairs deps, where each pair [a, b] means:

  • Task a must be completed before task b can start.

You can run any number of tasks in parallel as long as their prerequisites are satisfied.

Input

  • Integer n.
  • 2D array/list deps of pairs [a, b].

Output

Return the minimum total time (number of time units) required to finish all tasks.

Notes

  • If the dependency graph contains a cycle (tasks cannot be completed), specify what you would return (e.g., -1) and implement accordingly.

Example

If n = 3 and deps = [[1,3],[2,3]], tasks 1 and 2 can run in parallel in time 1, then task 3 runs in time 2, so the answer is 2.