Course Schedule with Topological Sort

Question

Given prerequisites for courses, determine if all courses can be finished and return a valid order. Tests topological sorting and cycle detection in directed graphs.

Codemia · Accepted Answer

This problem can be solved using **topological sorting** on a directed graph. The courses represent vertices and the prerequisites represent directed edges. The goal is to determine if there exists a valid order to take all courses, which translates to checking for cycles in the graph. If a cycle exists, it would indicate that a course depends on itself indirectly, making it impossible to complete all courses.

1. **Graph Representation**: Use an adjacency list to represent the directed graph where each course has a list of its prerequisites.
2. **In-degree Tracking**: Calculate the in-degree (number of prerequisites) for each course.
3. **Queue Initialization**: Initialize a queue with all courses that have an in-degree of 0 (no prerequisites).
4. **Topological Sort Process**:
   - While the queue is not empty:
     - Dequeue a course, add it to the result list.
     - For each of its neighbors (dependent courses), reduce their in-degree by 1. If any neighbor's in-degree becomes 0, enqueue it.
5. **Cycle Detection**: After processing, if the number of courses in the result list is equal to the total number of courses, return the result. Otherwise, return an empty list indicating that not all courses can be completed.

Here is the Python implementation of the above approach:
```python
from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses

# Build the graph and in-degree array
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

# Initialize the queue with courses that have no prerequisites
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    order = []

while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

# Check if we were able to complete all courses
    return order if len(order) == numCourses else []
```

The time complexity of this solution is **O(V + E)**, where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is because we traverse each vertex and each edge once. The space complexity is also **O(V + E)** due to the storage of the graph and in-degree array.

1. **No Courses**: If `numCourses` is 0, the output should be an empty list, as there are no courses to schedule. 
2. **Single Course with No Prerequisites**: If there is one course with no prerequisites, the output should be `[0]`.
3. **Multiple Courses with Circular Dependency**: If there is a cycle in prerequisites (e.g., `[[0, 1], [1, 0]]`), the output should be an empty list indicating that not all courses can be completed.

Course Schedule with Topological Sort

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string