How should I practice Find a Valid Course Completion Order?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Find a Valid Course Completion Order associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Find a Valid Course Completion Order

Google● MediumINTERNNEW GRADONSITE INTERVIEW

Learn

Problem statement

There are numCourses courses labeled from 0 to numCourses - 1. Each pair [course, prerequisite] means that prerequisite must be completed before course.

Return the lexicographically smallest order that completes every course. At each step, choose the smallest numbered course whose prerequisites have all been completed. If a directed cycle makes it impossible to complete every course, return an empty array.

Function

findCourseOrder(numCourses: int, prerequisites: int[][]) → int[]

Examples

Example 1

numCourses = 4prerequisites = [[1,0],[2,0],[3,1],[3,2]]return = [0,1,2,3]

Course 0 unlocks courses 1 and 2. Choosing 1 first makes the complete order lexicographically smallest.

Example 2

numCourses = 5prerequisites = [[2,0],[2,1],[3,1]]return = [0,1,2,3,4]

Courses 0, 1, and 4 initially have zero indegree. The smallest available course is always chosen.

Example 3

numCourses = 2prerequisites = [[1,0],[0,1]]return = []

The two courses form a directed cycle, so no complete order exists.

Constraints

1 <= numCourses <= 2000.
0 <= prerequisites.length <= 5000.
prerequisites[i].length == 2.
0 <= course, prerequisite < numCourses.
Every prerequisite pair is unique, and a course is never its own prerequisite.