Solving Adobe SDE 2 Interview Question: Course Schedule II

Hey there! I'm Shishir, a Director of Technology at Target and a former Technical Lead at Adobe. In this article, we’ll discuss a coding problem that's been asked at Adobe SDE 2 interviews.

This problem is about figuring out the order in which you should take a series of courses, given their prerequisites.

It's a classic example of using graph theory and topological sorting in computer science.

Let's dive in and explore how we can tackle this problem step by step.

Problem Statement: Course Schedule II

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1.

You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: [0,1]

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [0,2,1,3]

Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.

So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3

Input: numCourses = 1, prerequisites = []

Output: [0]

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

Solution

To solve the "Course Schedule II" problem, we can use a graph-based approach, specifically Topological Sorting.

The idea is to represent the courses and their prerequisites as a directed graph, where each vertex represents a course, and each edge (a, b) represents that course b is a prerequisite for course a.

The goal is to find a topological order of the courses, which is an ordering of the vertices in a directed graph such that for every directed edge (a, b), vertex a comes before b in the ordering.

A course schedule is possible if and only if the graph has no cycles.

We can detect cycles and find a topological order using Depth-First Search (DFS) or by using Kahn's algorithm (a BFS approach). Here, I'll demonstrate the solution using DFS:

def findOrder(numCourses, prerequisites):
    # Create a graph using an adjacency list representation
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    # States: 0 = unvisited, 1 = visiting, 2 = visited
    visit = [0] * numCourses
    order = []

    def dfs(course):
        if visit[course] == 1:  # Cycle detected
            return False
        if visit[course] == 2:  # Already visited
            return True

        visit[course] = 1  # Mark as visiting
        for prereq in graph[course]:
            if not dfs(prereq):
                return False
        visit[course] = 2  # Mark as visited
        order.append(course)  # Add to topological order
        return True

    # Try to visit each course
    for course in range(numCourses):
        if not dfs(course):
            return []  # Cycle detected, return empty list

    return order

# Example usage
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
print(findOrder(numCourses, prerequisites))

📌  Graph Representation: We first convert the list of prerequisites into a graph represented as an adjacency list. Each course points to its prerequisites.

📌  DFS and Cycle Detection: We use DFS to traverse the graph. For each course, we mark it as visiting (state 1).

If we encounter a course that is already in the visiting state during DFS, it means we've detected a cycle, and it's impossible to complete all courses.

If a course is in the visited state (state 2), it means we've already processed it, and we can skip it.

📌  Topological Order: During the DFS, once we finish visiting all prerequisites for a course, we mark it as visited (state 2) and add it to the topological order.

This ensures that a course is added to the order only after all its prerequisites are added.

📌  Detecting Impossible Schedules: If a cycle is detected at any point (meaning it's impossible to take all courses due to circular dependencies), we immediately return an empty list.

📌  Returning the Order: If no cycles are detected, we return the topological order of courses, which represents a valid sequence in which all courses can be completed.

This approach ensures that we correctly handle all prerequisites and detect any impossible course schedules due to circular dependencies.

********************

I hope you found this breakdown of the Course Schedule II question helpful. If you're preparing for Adobe interviews or just want to practice more problems like this, I'd be happy to help.

Feel free to book a free trial session with me.

I'm always excited to connect with fellow engineers and share what I've learned. Don't hesitate to get in touch, and good luck with your coding journey!