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 Onsite 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 Earliest Completion Times | Netflix Coding Question

Compute Earliest Completion Times

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given `n` tasks numbered from `0` to `n - 1`. Each task `i` has a positive duration `duration[i]`. You are also given a list of prerequisite relationships `prerequisites`, where `[a, b]` means task `a` must be fully completed before task `b` can start. Assume there are unlimited workers, so any number of tasks may run in parallel as long as their prerequisites are satisfied. Implement a function that returns: - the earliest completion time for every task, and - the minimum total time required to complete all tasks. If the prerequisite graph contains a cycle, return an error or a special value indicating that the schedule is impossible. Example: ```text n = 4 duration = [3, 2, 4, 1] prerequisites = [[0, 2], [1, 2], [2, 3]] Task 0 finishes at time 3. Task 1 finishes at time 2. Task 2 can start after both 0 and 1 finish, so it starts at time 3 and finishes at time 7. Task 3 starts at time 7 and finishes at time 8. Return earliestFinish = [3, 2, 7, 8], totalTime = 8. ```

Quick Answer: This question evaluates understanding of directed acyclic graphs, dependency resolution, computation of earliest task completion times, and cycle detection within prerequisite relationships.

You are given `n` tasks numbered from `0` to `n - 1`. Each task `i` has a positive duration `duration[i]`. You are also given prerequisite relationships `prerequisites`, where `[a, b]` means task `a` must be fully completed before task `b` can start. There are unlimited workers, so any number of tasks may run in parallel as long as their prerequisites are satisfied. Return a tuple `(earliest_finish, total_time)` where: - `earliest_finish[i]` is the earliest time task `i` can be completed, and - `total_time` is the minimum time required to finish all tasks. If the prerequisite graph contains a cycle, return `None` to indicate that the schedule is impossible.

Constraints

`0 <= n <= 200000`
`len(duration) == n`
`1 <= duration[i] <= 10^9` for each valid `i`
`0 <= len(prerequisites) <= 200000`
Each prerequisite is a pair `[a, b]` with `0 <= a, b < n`

Examples

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

Expected Output: ([3, 2, 7, 8], 8)

Explanation: Tasks 0 and 1 can run immediately, finishing at 3 and 2. Task 2 starts after both are done, so it starts at 3 and finishes at 7. Task 3 finishes at 8.

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

Expected Output: ([5, 1, 2], 5)

Explanation: With no prerequisites, all tasks run in parallel. Each task finishes after its own duration, and the total time is the maximum of those values.

Input: (0, [], [])

Expected Output: ([], 0)

Explanation: There are no tasks, so the earliest finish list is empty and the total time is 0.

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

Expected Output: ([2, 4, 3, 5, 9, 11], 11)

Explanation: Tasks 0, 1, and 2 finish at 2, 4, and 3. Task 3 starts at 4 and finishes at 5. Task 4 starts at 4 and finishes at 9. Task 5 starts at 9 and finishes at 11.

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

Expected Output: None

Explanation: The prerequisites form a cycle, so no valid schedule exists.

Hints

A valid schedule exists only if the prerequisite graph is a DAG. Think about using topological sorting to process tasks in dependency order.
For each task, track the maximum completion time among all of its prerequisites. Its own earliest finish is that value plus its duration.

Quick Overview

This question evaluates understanding of directed acyclic graphs, dependency resolution, computation of earliest task completion times, and cycle detection within prerequisite relationships.