Parallel Courses

Medium

Google

3 views

Topics:

GraphsDynamic ProgrammingGreedy Algorithms

You are given an integer n, which represents the number of courses you have to take, labeled from 1 to n. You are also given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. You need to find the minimum number of semesters to take all courses. Each semester, you can take any number of courses as long as you have taken all the prerequisites for the course. If it is impossible to take all the courses due to a cycle, return -1.

For example:

If n = 3 and prerequisites = [[1,3],[2,3]], this means you need to take courses 1 and 2 before course 3. You can take courses 1 and 2 in the first semester, and course 3 in the second semester, so the answer is 2.
If n = 3 and prerequisites = [[1,2],[2,3],[3,1]], this means you need to take course 2 before course 1, course 3 before course 2, and course 1 before course 3. Since this creates a cycle, it is impossible to finish all courses, so the answer is -1.
If n = 1 and prerequisites = [], this means there is only one course and no prerequisites. You can take this course in the first semester, so the answer is 1.

Can you provide an algorithm to find the minimum number of semesters required to take all courses, considering the prerequisites? Explain the time and space complexity of your solution. Consider edge cases, such as cyclic dependencies and empty prerequisite lists.

Parallel Courses

Medium

Google

3 views

Topics:

GraphsDynamic ProgrammingGreedy Algorithms

You are given an integer n, which represents the number of courses you have to take, labeled from 1 to n. You are also given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. You need to find the minimum number of semesters to take all courses. Each semester, you can take any number of courses as long as you have taken all the prerequisites for the course. If it is impossible to take all the courses due to a cycle, return -1.

For example:

If n = 3 and prerequisites = [[1,3],[2,3]], this means you need to take courses 1 and 2 before course 3. You can take courses 1 and 2 in the first semester, and course 3 in the second semester, so the answer is 2.
If n = 3 and prerequisites = [[1,2],[2,3],[3,1]], this means you need to take course 2 before course 1, course 3 before course 2, and course 1 before course 3. Since this creates a cycle, it is impossible to finish all courses, so the answer is -1.
If n = 1 and prerequisites = [], this means there is only one course and no prerequisites. You can take this course in the first semester, so the answer is 1.

Can you provide an algorithm to find the minimum number of semesters required to take all courses, considering the prerequisites? Explain the time and space complexity of your solution. Consider edge cases, such as cyclic dependencies and empty prerequisite lists.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of course numbers? Can they be negative or zero?
Is it possible for there to be cycles in the dependencies (making it impossible to complete all courses)? If so, what should the function return?
If multiple valid schedules exist, is any valid schedule acceptable, or is there a specific ordering or prioritization I should follow?
What is the expected return value if there are no courses (n = 0)?
Can a course have no prerequisites? If so, does that mean it can be taken in any semester?

Brute Force Solution

Approach

The brute force approach to figuring out the minimum number of semesters to complete courses involves trying every possible order to take the courses in. We check if each order is valid, meaning no course is taken before its prerequisites. After checking, we select the best valid order based on how many semesters it takes.

Here's how the algorithm would work step-by-step:

Imagine we have a random ordering of all the courses.
We'll check if this ordering respects all the prerequisites. In other words, for every course, we make sure we've taken all its prerequisite courses before we take it.
If the ordering doesn't respect the prerequisites, we throw it away and try a different random ordering.
If the ordering does respect all the prerequisites, we figure out the number of semesters it would take to complete all the courses in that order. We would essentially go through each course, and assign it to the earliest semester possible given that all its prerequisites are complete.
We keep track of the order that takes the least amount of semesters.
Repeat the process of creating an order, checking its validity, determining its semester count, and comparing to the lowest count so far, a huge number of times to find the optimal order.

Code Implementation

import random

def parallel_courses_brute_force(number_of_courses, prerequisites):
    best_semesters = float('inf')

    for _ in range(1000): # Try many random orderings to find the best
        course_order = list(range(1, number_of_courses + 1))
        random.shuffle(course_order)

        if is_valid_order(course_order, prerequisites, number_of_courses):
            #If course order is valid find the number of semesters needed
            semesters_needed = calculate_semesters(course_order, prerequisites)
            best_semesters = min(best_semesters, semesters_needed)

    if best_semesters == float('inf'):
        return -1
    return best_semesters

def is_valid_order(course_order, prerequisites, number_of_courses):
    course_index_map = {course: index for index, course in enumerate(course_order)}

    for course, prereqs in enumerate([[] for _ in range(number_of_courses + 1)]):
      for pre, post in prerequisites:
        if post == course + 1:
          prereqs.append(pre)

    for post_course in range(1, number_of_courses + 1):
        prerequisites_for_course = []
        for pre, post in prerequisites:
          if post == post_course:
            prerequisites_for_course.append(pre)

        for pre_course in prerequisites_for_course:
            #Check if all prereqs are taken before current course
            if course_index_map[pre_course] > course_index_map[post_course]:
                return False

    return True

def calculate_semesters(course_order, prerequisites):
    course_semesters = {}
    for course in course_order:
        #Assign the earliest semester possible to each course
        max_prereq_semester = 0
        for pre, post in prerequisites:
            if post == course:
                max_prereq_semester = max(max_prereq_semester, course_semesters[pre])

        course_semesters[course] = max_prereq_semester + 1

    return max(course_semesters.values())

Big(O) Analysis

Time Complexity

O(n! * n^2) – The algorithm explores all possible orderings of the n courses, which leads to n! permutations. For each permutation, we need to check if the ordering respects the prerequisites. Checking prerequisites involves iterating through each course and comparing it to its prerequisites which takes O(n) time. Furthermore, determining the semester count requires assigning courses to semesters, which can take up to O(n) in the worst case, resulting in O(n) + O(n) = O(n). Consequently, checking a single permutation takes O(n). Therefore, the total time complexity is O(n! * n).

Space Complexity

O(N) – The described brute force approach involves generating random orderings of courses. Storing one such ordering requires space proportional to the number of courses, N. The algorithm also keeps track of the best valid order found so far, requiring another array of size N to store the course order. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The best way to solve this is to think about doing courses in order, taking courses as soon as you can. We need to figure out the fewest number of semesters needed to finish all courses while following the prerequisites.

Here's how the algorithm would work step-by-step:

First, figure out which courses don't have any courses you need to take before them. These are your starting points.
Now, think about doing these courses in parallel in your first semester.
Once you've 'taken' those courses, look at what courses they unlock for the next semester.
Repeat the process of taking as many courses as you can each semester, based on what's been unlocked, until all courses are completed.
Keep track of how many semesters it took. If you find a situation where you can't take all the courses because of a cycle, it's impossible to finish, so indicate that.

Code Implementation

def parallel_courses(number_of_courses, prerequisites):
    indegree = [0] * number_of_courses
    adjacency_list = [[] for _ in range(number_of_courses)]

    for course, prerequisite in prerequisites:
        indegree[course - 1] += 1
        adjacency_list[prerequisite - 1].append(course - 1)

    # Identify courses with no prerequisites
    queue = [i for i in range(number_of_courses) if indegree[i] == 0]

    semesters = 0
    courses_taken = 0

    while queue:
        semesters += 1
        next_queue = []

        # Process all courses that can be taken in parallel
        for course in queue:
            courses_taken += 1

            # Update indegrees of dependent courses
            for next_course in adjacency_list[course]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    next_queue.append(next_course)

        # Courses for the next semester
        queue = next_queue

    # Check for cycle if not all courses are taken
    if courses_taken != number_of_courses:
        return -1

    # Total semesters needed to finish all courses
    return semesters

Big(O) Analysis

Time Complexity

O(n + e) – The algorithm begins by identifying courses with no prerequisites, which takes O(n) time, where n is the number of courses. Then, it iteratively processes courses, simulating semesters. In each semester, we effectively traverse the adjacency list to update in-degrees (number of prerequisites) and identify unlocked courses. This traversal is proportional to the number of prerequisites, which is represented as 'e' (the number of edges, or dependencies between courses). The algorithm continues until all courses are completed, or a cycle is detected. The processing of all courses and dependencies combined gives a runtime of O(n + e).

Space Complexity

O(N + P) – The algorithm uses auxiliary space to store the in-degree of each course (N, where N is the number of courses), which requires an array of size N. Additionally, a queue is used to hold courses that are ready to be taken, and in the worst case, this queue could contain all courses, resulting in a space complexity of O(N). The algorithm may also use a list of prerequisites for each course (P, where P is the number of prerequisites across all courses), meaning extra space is required to keep track of these prerequisites. Thus, the overall auxiliary space complexity is O(N + P).

Edge Cases

Case	How to Handle
Empty input: n = 0, prerequisites = []	Return an empty list or handle it as an already completed course list, depending on problem requirements.
Single course with no prerequisites: n = 1, prerequisites = []	Return a list containing only that single course [0].
All courses depend on each other, creating a cycle	Detect cycles in the graph and return an empty list indicating that the courses cannot be finished.
Maximum number of courses and prerequisites (n is very large)	Ensure the algorithm uses memory efficiently and avoid excessive recursion to prevent stack overflow, potentially using iterative topological sort with a queue.
A course has no dependencies but other courses depend on it	Add courses with no dependencies to the starting queue for topological sort.
Duplicate prerequisites for the same course	The data structure storing the prerequisites should treat duplicates as a single dependency.
Input contains invalid course numbers (e.g., negative numbers or numbers greater than n-1)	Validate course numbers to ensure they are within the valid range and handle or throw an error if invalid values are found.
Multiple valid course orders exist	The algorithm should return one valid order; the specific order might depend on the implementation of the topological sort.