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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Netflix.

What role is this question designed for?

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

Compute Minimum Task Completion Time | Netflix Coding Question

Compute Minimum Task Completion Time

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given `n` tasks numbered from `0` to `n - 1`. Each task `i` takes `durations[i]` units of time to execute. You are also given a list of directed dependencies, where each pair `[a, b]` means task `a` must finish before task `b` can start. Any number of tasks may run in parallel as long as all of their prerequisites have completed. Implement a function: ```python def min_completion_time(n: int, durations: list[int], dependencies: list[list[int]]) -> int: pass ``` Return the minimum total time required to complete all tasks. If the dependency graph contains a cycle, return `-1` because it is impossible to complete all tasks. You should be prepared to explain a BFS/topological-sort approach, handle edge cases such as cycles and disconnected tasks, and walk through your own test cases. Follow-up: How would you solve the same problem using DFS? You do not need to write the full code; explain the idea clearly.

Quick Answer: This question evaluates understanding of graph algorithms (topological sort and DFS), dependency scheduling, cycle detection, and critical-path computation for tasks with durations.

Part 1: Minimum Task Completion Time with BFS Topological Sort

You are given n tasks numbered from 0 to n - 1. Task i takes durations[i] units of time. You are also given directed dependencies, where each pair [a, b] means task a must finish before task b can start. Any number of tasks may run in parallel as long as all of their prerequisites are complete. Implement a function solution(n, durations, dependencies) that returns the minimum total time required to complete all tasks. If the dependency graph contains a cycle, return -1. You should solve this version using a BFS / topological-sort approach.

Constraints

0 <= n <= 100000
len(durations) == n
0 <= durations[i] <= 10^9
0 <= len(dependencies) <= 200000
Each dependency is a pair [a, b] with 0 <= a, b < n

Examples

Input: (3, [3, 2, 5], [[0, 2], [1, 2]])

Expected Output: 8

Explanation: Tasks 0 and 1 run in parallel. Task 2 starts after both are done, so it starts at time 3 and finishes at time 8.

Input: (5, [1, 2, 3, 4, 2], [[0, 2], [1, 2], [2, 3]])

Expected Output: 9

Explanation: Task 2 must wait for tasks 0 and 1, so it finishes at time 5. Then task 3 finishes at time 9. Task 4 is independent and finishes earlier.

Input: (3, [1, 1, 1], [[0, 1], [1, 2], [2, 0]])

Expected Output: -1

Explanation: The dependencies form a cycle, so no valid ordering exists.

Input: (0, [], [])

Expected Output: 0

Explanation: There are no tasks, so the total completion time is 0.

Hints

Use indegree counts to find which tasks can start immediately.
As you process tasks in topological order, track the earliest finish time for each task based on the maximum finish time among its prerequisites.

Part 2: Minimum Task Completion Time with DFS Memoization

You are given n tasks numbered from 0 to n - 1. Task i takes durations[i] units of time. You are also given directed dependencies, where each pair [a, b] means task a must finish before task b can start. Any number of tasks may run in parallel as long as all of their prerequisites are complete. Implement a function solution(n, durations, dependencies) that returns the minimum total time required to complete all tasks. If the dependency graph contains a cycle, return -1. Solve this version using DFS with memoization and cycle detection.

Constraints

0 <= n <= 100000
len(durations) == n
0 <= durations[i] <= 10^9
0 <= len(dependencies) <= 200000
Each dependency is a pair [a, b] with 0 <= a, b < n

Examples

Input: (4, [2, 1, 4, 3], [[0, 2], [1, 2], [2, 3]])

Expected Output: 9

Explanation: Tasks 0 and 1 can run first. Task 2 must wait for both, so it finishes at time 6. Task 3 then finishes at time 9.

Input: (4, [5, 2, 1, 4], [])

Expected Output: 5

Explanation: With no dependencies, all tasks run in parallel, so the answer is the maximum single duration.

Input: (2, [3, 4], [[0, 1], [1, 0]])

Expected Output: -1

Explanation: Tasks 0 and 1 depend on each other, forming a cycle.

Input: (0, [], [])

Expected Output: 0

Explanation: No tasks means no time is needed.

Hints

Think of each task's completion time as its own duration plus the maximum completion time among all of its prerequisites.
Use a 3-state DFS marking scheme: unvisited, visiting, and fully processed. Re-entering a visiting node means there is a cycle.

Quick Overview

This question evaluates understanding of graph algorithms (topological sort and DFS), dependency scheduling, cycle detection, and critical-path computation for tasks with durations.