PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates competency in analyzing directed graphs and dependency resolution, focusing on cycle detection and the feasibility of ordering prerequisites for course completion.

  • hard
  • Uber
  • Coding & Algorithms
  • Software Engineer

Check feasibility of AI course schedule

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are designing a learning path for `n` AI-related courses, labeled from `0` to `n - 1`. Some courses have prerequisites. For example, to take course `b`, you may first need to finish course `a`. This can be represented as a directed edge `a -> b`. You are given: - An integer `n`, the number of courses. - A list `prerequisites` of pairs `[a, b]`, where each pair means: **to take course `b`, you must first complete course `a`**. You need to determine whether it is possible to finish **all** courses. Formally, model the courses as a directed graph: - Each course is a node. - Each prerequisite pair `[a, b]` is a directed edge from `a` to `b`. If the graph contains a cycle (e.g., `0 -> 1 -> 2 -> 0`), then there is no way to complete all courses because each course in the cycle depends on another in the cycle. ### Task Write an algorithm that: - Returns `true` if it is possible to complete all `n` courses given the prerequisites. - Returns `false` if it is **not** possible (i.e., if there is at least one cycle in the prerequisite graph). **Constraints** (typical interview constraints; you may assume something like): - `1 <= n <= 10^5`. - `0 <= prerequisites.length <= 10^5`. - `0 <= a, b < n` for every pair `[a, b]`. Your algorithm should run in **O(n + m)** time, where `m = prerequisites.length`, and use **O(n + m)** extra space. You may use any standard graph traversal technique (e.g., DFS or BFS/topological sort).

Quick Answer: This question evaluates competency in analyzing directed graphs and dependency resolution, focusing on cycle detection and the feasibility of ordering prerequisites for course completion.

Return true if all courses can be completed, false if prerequisites contain a cycle.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

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

Expected Output: True

Explanation: Acyclic.

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

Expected Output: False

Explanation: Cycle.

Input: (3, [])

Expected Output: True

Explanation: No prerequisites.

Hints

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.
Last updated: Jun 27, 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

  • Thread-Safe Token-Bucket Rate Limiter - Uber
  • Quadtree for 2D Geospatial Points - Uber
  • Group Anagrams - Uber
  • Deep Equality of Two Records - Uber (medium)
  • Shortest Path in a Grid with Blocked Cells - Uber (medium)