Uber·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Uber ML Engineer coding round, one question the whole time. The problem was a graph/topological sort thing dressed up as task scheduling, which I thought I handled okay but I'm still not sure how I did.

Questions Asked (1)

You have n tasks labeled 1 through n, each taking 1 unit of time. Given a list of prerequisite pairs where [a, b] means task a must finish before task b starts, and assuming you can run any number of tasks in parallel as long as their prerequisites are met, return the minimum total time to complete all tasks. Also handle cycles in the dependency graph.

Algorithms & Data Structures

Author's notes

Basically asking for the longest path in a DAG, which is just the critical path.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tasks and prerequisites as a directed graph, then compute the longest path (critical path) using topological sort. If a cycle is detected, return an error or -1 to indicate impossibility. The minimum total time equals the number of nodes in the longest dependency chain.

Pro tip: Explicitly state that you're computing the critical path, not just counting levels, and mention that cycle detection is naturally handled by Kahn's algorithm (if processed nodes < n, there's a cycle). This shows you understand both the algorithmic and practical implications.

1. Model as a Directed Graph

Represent tasks as nodes and prerequisites as directed edges (a -> b means a must finish before b). Build an adjacency list and compute in-degrees for all nodes.

2. Topological Sort with Kahn's Algorithm

Use a queue to process nodes with in-degree 0, updating in-degrees of neighbors. Track the number of processed nodes to detect cycles.

3. Compute Longest Path (Critical Path)

While processing, maintain a distance array where dist[v] = max(dist[v], dist[u] + 1) for each edge u->v. The answer is the maximum distance value.

4. Handle Cycles

If the number of processed nodes is less than n, a cycle exists. Return -1 or an error indicating the tasks cannot be completed.

5. Return the Result

If no cycle, return the maximum distance (minimum total time). If cycle, return -1.

Key Points to Mention

Directed Acyclic Graph (DAG) and topological sorting
Kahn's algorithm for topological sort and cycle detection
Longest path in a DAG (critical path method)
Time complexity: O(n + m) where n is number of tasks and m is number of prerequisites
Space complexity: O(n + m) for adjacency list and auxiliary arrays
Parallel execution assumption: tasks with no dependencies can run simultaneously, so total time is the longest chain

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.