Course Schedule IV

MediumGraphstopological sort

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are numCourses courses labeled 0 to numCourses - 1. Each entry prerequisites[i] = [a, b] means course a must be taken before course b. Prerequisite relationships chain: if a comes before b and b comes before c, then a is also a prerequisite of c. You are also given queries, where queries[j] = [u, v] asks whether course u is a (direct or indirect) prerequisite of course v. Return a boolean array whose j-th entry answers query j. The prerequisite graph has no cycles and no repeated pairs. A course is never considered its own prerequisite, and queries always have u != v.

Examples

Input: numCourses = 3, prerequisites = [[0,1],[1,2]], queries = [[0,2],[2,0],[1,0]]
Output: [true,false,false]
`0 -> 1 -> 2`, so `0` is a prerequisite of `2`; nothing leads back to `0`.
Input: numCourses = 4, prerequisites = [], queries = [[0,1],[3,2]]
Output: [false,false]
With no prerequisites, no course depends on another.

Constraints

  • 2 <= numCourses <= 100
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1) / 2
  • `prerequisites[i] = [a, b]`, `a != b`, all pairs unique, the graph is acyclic
  • 1 <= queries.length <= 10^4
  • `queries[j] = [u, v]`, `u != v`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More topological sort problems