Find the Critical Path
Company: Modular
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a project represented as a directed acyclic graph of tasks. Each task has:
- a unique task name
- a list of prerequisite task names
- a positive duration
The input format is:
```python
TASK(name, dependencies, duration)
```
A task may start only after all of its dependencies have finished.
Write a function that, given a list of tasks, returns:
1. the **critical path value**: the maximum total duration needed along any valid dependency chain
2. one corresponding **critical path**: the ordered list of task names on that longest path
If multiple critical paths have the same total duration, returning any one of them is acceptable.
Example inputs:
```python
graph1 = [
TASK("A", [], 3),
TASK("B", [], 5),
TASK("C", ["A"], 5),
]
graph2 = [
TASK("A", [], 2),
TASK("B", ["A"], 4),
TASK("C", ["B"], 3),
TASK("D", ["C"], 6),
]
graph3 = [
TASK("A", [], 3),
TASK("B", ["A"], 2),
TASK("C", ["A"], 7),
TASK("D", ["B", "C"], 4),
TASK("E", ["D"], 2),
]
graph4 = [
TASK("A", [], 3),
TASK("B", [], 8),
TASK("C", ["A"], 2),
TASK("D", ["C"], 5),
TASK("E", ["B"], 1),
TASK("F", ["D", "E"], 4),
]
graph5 = [
TASK("A", [], 1),
TASK("B", ["A"], 2),
TASK("C", ["A"], 5),
TASK("D", ["B"], 4),
TASK("E", ["C"], 3),
TASK("F", ["D", "E"], 3),
TASK("G", ["F"], 6),
TASK("H", ["C"], 2),
TASK("I", ["H"], 7),
TASK("J", ["G", "I"], 2),
]
graph6 = [
TASK("M", [], 4),
TASK("N", ["M"], 3),
TASK("O", ["N"], 2),
TASK("P", ["M"], 6),
TASK("Q", ["O", "P"], 5),
TASK("R", ["Q"], 4),
TASK("S", ["N"], 1),
TASK("T", ["S", "R"], 2),
]
```
Assume the dependency graph is valid and acyclic.
Quick Answer: This question evaluates competency in graph algorithms and project scheduling, specifically reasoning about directed acyclic graphs, task dependencies, and accumulation of task durations to identify a critical path.
You are given a list of project tasks. Each task is represented as a tuple `(name, prerequisites, duration)`, where `name` is a unique task ID, `prerequisites` is a list of task names that must finish before this task can start, and `duration` is the time needed to complete the task.
The tasks form a directed acyclic graph (DAG). The **critical path** is the dependency chain with the maximum total duration. Your job is to return both:
1. the critical path value (the longest total duration), and
2. the actual critical path as a list of task names in execution order.
If multiple critical paths have the same total duration, return the lexicographically smallest path when comparing the full list of task names.
For an empty task list, return `(0, [])`.
Constraints
- 0 <= number of tasks <= 2000
- 0 <= total number of prerequisite links <= 10000
- Each task name is a unique string
- The dependency graph is a DAG
- 1 <= duration <= 10^6 for each task
Examples
Input: []
Expected Output: (0, [])
Explanation: There are no tasks, so the critical path has duration 0 and an empty path.
Input: [('A', [], 3), ('B', ['A'], 2), ('C', ['A'], 5)]
Expected Output: (8, ['A', 'C'])
Explanation: Path A -> B has total duration 5, while A -> C has total duration 8. The critical path is ['A', 'C'].
Hints
- For each task, its best finish time is its own duration plus the maximum best finish time among its prerequisites.
- Process the tasks in topological order so that all prerequisite results are known before computing a task.