PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches
|Home/Coding & Algorithms/Uber

Compute minimal time to finish dependent tasks

Last updated: Mar 29, 2026

Quick Overview

This question evaluates understanding of graph algorithms and scheduling, specifically reasoning about task dependencies, parallel execution, and cycle detection in directed graphs.

  • medium
  • Uber
  • Coding & Algorithms
  • Machine Learning Engineer

Compute minimal time to finish dependent tasks

Company: Uber

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Coding: Task Scheduling With Prerequisites (Parallel Allowed) You have `n` tasks labeled `1..n`. Each task takes **exactly 1 unit of time** to complete. Some tasks have prerequisites. You are given a list of prerequisite pairs `deps`, where each pair `[a, b]` means: - Task `a` must be completed **before** task `b` can start. You can run **any number of tasks in parallel** as long as their prerequisites are satisfied. ### Input - Integer `n`. - 2D array/list `deps` of pairs `[a, b]`. ### Output Return the **minimum total time** (number of time units) required to finish all tasks. ### Notes - If the dependency graph contains a cycle (tasks cannot be completed), specify what you would return (e.g., `-1`) and implement accordingly. ### Example If `n = 3` and `deps = [[1,3],[2,3]]`, tasks 1 and 2 can run in parallel in time 1, then task 3 runs in time 2, so the answer is 2.

Quick Answer: This question evaluates understanding of graph algorithms and scheduling, specifically reasoning about task dependencies, parallel execution, and cycle detection in directed graphs.

Related Interview Questions

  • Implement Minesweeper and Word Search - Uber (medium)
  • Implement Store Autocomplete - Uber (medium)
  • Implement Cache Eviction And Seat Assignment - Uber (medium)
  • Schedule Non-Overlapping Meetings Efficiently - Uber (hard)
  • Evaluate an Arithmetic Expression - Uber
Uber logo
Uber
Dec 15, 2025, 12:00 AM
Machine Learning Engineer
Onsite
Coding & Algorithms
8
0

Coding: Task Scheduling With Prerequisites (Parallel Allowed)

You have n tasks labeled 1..n. Each task takes exactly 1 unit of time to complete. Some tasks have prerequisites.

You are given a list of prerequisite pairs deps, where each pair [a, b] means:

  • Task a must be completed before task b can start.

You can run any number of tasks in parallel as long as their prerequisites are satisfied.

Input

  • Integer n .
  • 2D array/list deps of pairs [a, b] .

Output

Return the minimum total time (number of time units) required to finish all tasks.

Notes

  • If the dependency graph contains a cycle (tasks cannot be completed), specify what you would return (e.g., -1 ) and implement accordingly.

Example

If n = 3 and deps = [[1,3],[2,3]], tasks 1 and 2 can run in parallel in time 1, then task 3 runs in time 2, so the answer is 2.

Comments (0)

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Uber•More Machine Learning Engineer•Uber Machine Learning Engineer•Uber Coding & Algorithms•Machine Learning Engineer Coding & Algorithms
PracHub

Master your tech interviews with 7,500+ 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
  • Compare Platforms
  • Discord Community

Support

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

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.