Bird
Raised Fist0

Consider the following Python code implementing the optimal approach for minimum semesters. Given n = 3 and relations = [[1,3],[2,3]], what is the value of semester returned by the function?

easy🧾 Code Trace Q12 of Q15
Topological Sort - Parallel Courses (Minimum Semesters)
Consider the following Python code implementing the optimal approach for minimum semesters. Given n = 3 and relations = [[1,3],[2,3]], what is the value of semester returned by the function?
from collections import deque, defaultdict

def min_semesters_optimal(n, relations):
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for u, v in relations:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    semester = 0
    processed = 0

    while queue:
        semester += 1
        for _ in range(len(queue)):
            course = queue.popleft()
            processed += 1
            for nei in graph[course]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

    return semester if processed == n else -1

print(min_semesters_optimal(3, [[1,3],[2,3]]))
A2
B1
C3
D-1
Step-by-Step Solution
  1. Step 1: Initialize graph and indegree

    Courses 1 and 2 have indegree 0, course 3 has indegree 2.
  2. Step 2: Process BFS levels

    Semester 1: process courses 1 and 2 (both indegree 0), decrement indegree of 3 twice -> indegree[3] becomes 0, add 3 to queue. Semester 2: process course 3.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Two BFS levels -> 2 semesters [OK]
Quick Trick: Courses with zero indegree processed per semester [OK]
Common Mistakes:
MISTAKES
  • Counting each course as a separate semester
  • Off-by-one error in semester increment
  • Returning -1 incorrectly when all courses processed
Trap Explanation:
PITFALL
  • Some think each course is one semester ignoring parallelism; BFS processes all zero indegree nodes per semester.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute BFS topological sort and track variables.
Master "Parallel Courses (Minimum Semesters)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes