PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates competency in graph algorithms and scheduling, including dependency resolution, cycle detection, and aggregation of task durations; it belongs to the Coding & Algorithms domain and primarily tests practical application of algorithmic reasoning with conceptual understanding of precedence constraints.

  • medium
  • Snowflake
  • Coding & Algorithms
  • Software Engineer

Compute total time to finish all courses

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given `n` courses labeled `1..n`. Each course `i` takes `time[i]` units of time to complete. You are also given prerequisite relations `prereqs`, where each pair `[a, b]` means **course `a` must be completed before course `b` can be taken**. Courses are taken in **batches (rounds/semesters)** under the following rule: - At the **start** of a batch, you may start **any number of courses** whose prerequisites are already satisfied. - The batch **finishes only when all courses started in that batch finish**. - The duration of a batch is therefore `max(time[c])` over all courses `c` taken in that batch. - You can only start the next batch after the current batch finishes. ### Task Return the **minimum total time** required to finish all courses. ### Cycle condition If the prerequisite graph contains a cycle (so it is impossible to finish all courses), return `-1`. ## Example Suppose prerequisites imply two batches: first take courses `{1, 3}`, then take `{2, 4}` (e.g., edges `1 -> 2` and `3 -> 4`). - `time = [1, 10, 10, 1]` for courses `1..4` - Batch 1 duration: `max(1, 10) = 10` - Batch 2 duration: `max(10, 1) = 10` - Total = `20` ## Follow-up (variant scheduling rule) How would your approach change if courses can start **immediately when their prerequisites are satisfied**, without waiting for the rest of the current batch to finish (i.e., no batch barrier; courses can overlap asynchronously)? In that variant, return the minimum total completion time or `-1` if a cycle exists. ## Constraints (typical) - `1 <= n <= 2 * 10^5` - `0 <= prereqs.length <= 2 * 10^5` - `1 <= time[i] <= 10^9`

Quick Answer: This question evaluates competency in graph algorithms and scheduling, including dependency resolution, cycle detection, and aggregation of task durations; it belongs to the Coding & Algorithms domain and primarily tests practical application of algorithmic reasoning with conceptual understanding of precedence constraints.

Total Time to Finish All Courses (Batch Scheduling)

You are given `n` courses labeled `1..n`. Course `i` takes `time[i-1]` units of time to complete (1-indexed labels, 0-indexed time array). You are also given prerequisite relations `prereqs`, where each pair `[a, b]` means course `a` must be completed before course `b` can be taken. Courses are taken in **batches (rounds)** under the following rule: - At the start of a batch, you may start any number of courses whose prerequisites are already satisfied. - The batch finishes only when all courses started in that batch finish. - The duration of a batch is `max(time[c])` over all courses `c` taken in that batch. - You can only start the next batch after the current batch finishes. Return the **minimum total time** required to finish all courses. If the prerequisite graph contains a cycle (so it is impossible to finish all courses), return `-1`. **Example:** `n = 4`, `time = [1, 10, 10, 1]`, `prereqs = [[1, 2], [3, 4]]`. Batch 1 = {1, 3} with duration max(1, 10) = 10; Batch 2 = {2, 4} with duration max(10, 1) = 10. Total = 20.

Constraints

  • 1 <= n <= 2 * 10^5
  • 0 <= prereqs.length <= 2 * 10^5
  • 1 <= time[i] <= 10^9
  • Course labels are 1..n; time is 0-indexed (time[i-1] for course i)
  • Return -1 if the prerequisite graph contains a cycle

Examples

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

Expected Output: 20

Explanation: Batch 1 = {1, 3} duration max(1, 10) = 10; Batch 2 = {2, 4} duration max(10, 1) = 10. Total = 20.

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

Expected Output: 22

Explanation: A single chain 1->2->3->4, so four batches of one course each: 1 + 10 + 10 + 1 = 22.

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

Expected Output: 5

Explanation: Single course, one batch, duration 5.

Input: (3, [3, 7, 2], [])

Expected Output: 7

Explanation: No prerequisites, so all three start in one batch; duration max(3, 7, 2) = 7.

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

Expected Output: -1

Explanation: Courses 1 and 2 are mutually dependent (cycle). Impossible -> -1.

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

Expected Output: -1

Explanation: Three-node cycle 1->2->3->1. No course can start -> -1.

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

Expected Output: 15

Explanation: Batch 1 = {1, 2} max(2, 3) = 3; Batch 2 = {3} = 8; Batch 3 = {4, 5} max(1, 4) = 4. Total = 3 + 8 + 4 = 15.

Hints

  1. This is a level-by-level (BFS) topological sort. Each BFS level is exactly one batch.
  2. Process the queue one full level at a time: snapshot the current queue length, drain exactly that many nodes, and take the max time among them as that batch's duration.
  3. Detect a cycle by counting how many nodes you actually processed. If it's fewer than n, some nodes were never freed (their in-degree never hit 0), so a cycle exists -> return -1.
  4. Sum the per-batch maxima to get the answer.

Total Time to Finish All Courses (Async / Critical Path)

Same setup as the batch version: `n` courses labeled `1..n`, `time[i-1]` is the time for course `i`, and `prereqs` is a list of `[a, b]` pairs meaning course `a` must finish before course `b` can start. **Follow-up scheduling rule (no batch barrier):** a course may start **immediately** the moment all its prerequisites are finished, without waiting for any other course. Courses overlap asynchronously and there is no shared round. Return the **minimum total completion time** (the moment the last course finishes), or `-1` if the prerequisite graph contains a cycle. This is equivalent to the longest weighted path through the DAG, where each course contributes its own time. For a course `c`, its finish time is `time[c] + max(finish[p])` over all prerequisites `p` of `c` (or just `time[c]` if it has no prerequisites). The answer is the maximum finish time over all courses. **Example:** `n = 4`, `time = [1, 10, 10, 1]`, `prereqs = [[1, 2], [3, 4]]`. finish[1] = 1, finish[3] = 10, finish[2] = 1 + 10 = 11, finish[4] = 10 + 1 = 11. Answer = 11 (contrast with 20 in the batch version).

Constraints

  • 1 <= n <= 2 * 10^5
  • 0 <= prereqs.length <= 2 * 10^5
  • 1 <= time[i] <= 10^9
  • Course labels are 1..n; time is 0-indexed (time[i-1] for course i)
  • Return -1 if the prerequisite graph contains a cycle
  • Use 64-bit arithmetic: a chain of up to 2*10^5 courses each of time 10^9 can overflow 32-bit

Examples

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

Expected Output: 11

Explanation: finish[1]=1, finish[3]=10, finish[2]=1+10=11, finish[4]=10+1=11. Max = 11 (vs 20 in the batch version).

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

Expected Output: 22

Explanation: Single chain 1->2->3->4: finishes are 1, 11, 21, 22. Answer = 22 (same as batch here because it is one chain).

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

Expected Output: 5

Explanation: Single course finishes at time 5.

Input: (3, [3, 7, 2], [])

Expected Output: 7

Explanation: No prerequisites; each finishes at its own time. Max(3, 7, 2) = 7.

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

Expected Output: -1

Explanation: Mutual dependency between 1 and 2 -> cycle -> -1.

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

Expected Output: -1

Explanation: Three-node cycle -> -1.

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

Expected Output: 15

Explanation: finish[1]=2, finish[2]=3, finish[3]=max(2,3)+8=11, finish[4]=11+1=12, finish[5]=11+4=15. Max = 15.

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

Expected Output: 7

Explanation: finish[1]=5, finish[2]=5, finish[3]=max(5,5)+1=6, finish[4]=6+1=7. Max = 7.

Hints

  1. Without a batch barrier, each course finishes at time[c] + max(finish over its prerequisites). The answer is the maximum finish time across all courses -> this is the longest weighted path in the DAG.
  2. Do a topological sort (Kahn's algorithm). Seed roots (in-degree 0) with finish = their own time.
  3. When you pop a course c, relax each successor: finish[next] = max(finish[next], finish[c] + time[next]). Decrement its in-degree and enqueue it once the in-degree reaches 0.
  4. Cycle detection is the same as the batch version: if fewer than n nodes are processed, a cycle exists -> return -1.
  5. Watch for integer overflow in Java/C++ — accumulate finish times as 64-bit (long / long long).
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a JSON Parser - Snowflake (hard)
  • Solve Matrix and Array Distance Problems - Snowflake (medium)
  • Solve Array Distance and Wiki Navigation - Snowflake (medium)
  • Implement Document Predicate APIs - Snowflake (medium)
  • Find Shortest Wiki Click Path - Snowflake (medium)