How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Modular.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Modular during technical interviews.

Find the Critical Path | Modular Coding Question

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'].

Input: [('A', [], 2), ('B', ['A'], 4), ('C', ['B'], 3), ('D', ['C'], 6)]

Expected Output: (15, ['A', 'B', 'C', 'D'])

Explanation: There is a single chain A -> B -> C -> D, and its total duration is 2 + 4 + 3 + 6 = 15.

Input: [('Task1', [], 7)]

Expected Output: (7, ['Task1'])

Explanation: With only one task, that task itself is the critical path.

Input: [('A', [], 3), ('B', [], 3), ('C', ['A'], 2), ('D', ['B'], 2)]

Expected Output: (5, ['A', 'C'])

Explanation: Both ['A', 'C'] and ['B', 'D'] have total duration 5. The lexicographically smaller path is ['A', 'C'].

Input: [('A', [], 2), ('B', [], 2), ('C', ['A'], 3), ('D', ['B'], 3), ('E', ['C', 'D'], 4)]

Expected Output: (9, ['A', 'C', 'E'])

Explanation: Task E depends on both C and D. The longest prerequisite chain to E is tied between ['A', 'C'] and ['B', 'D'], each totaling 5 before E. Adding E gives total 9, and the lexicographically smaller full path is ['A', 'C', 'E'].

Input: [('A', [], 1), ('B', ['A'], 2), ('C', ['A'], 2), ('D', ['B', 'C'], 3)]

Expected Output: (6, ['A', 'B', 'D'])

Explanation: Both paths ['A', 'B', 'D'] and ['A', 'C', 'D'] total 6. Since B < C, ['A', 'B', 'D'] is lexicographically smaller.

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.

Quick Overview

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.