Bird
Raised Fist0

The following code attempts to compute the minimum semesters to complete all courses using BFS topological sort. Identify the bug that causes incorrect results or infinite loops.

medium🐞 Bug Identification Q14 of Q15
Topological Sort - Parallel Courses (Minimum Semesters)
The following code attempts to compute the minimum semesters to complete all courses using BFS topological sort. Identify the bug that causes incorrect results or infinite loops.
from collections import deque, defaultdict

def min_semesters_buggy(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
        course = queue.popleft()  # Bug here: processing one course per semester
        processed += 1
        for nei in graph[course]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    return semester if processed == n else -1
ALine with 'semester += 1' increments semester too early.
BLine with 'course = queue.popleft()' processes only one course per semester instead of all available.
CLine with 'indegree[nei] -= 1' incorrectly decrements indegree causing negative values.
DLine with 'queue = deque(...)' initializes queue incorrectly missing some zero indegree courses.
Step-by-Step Solution
  1. Step 1: Identify how courses are processed per semester

    The code processes only one course per semester by popping one element from the queue.
  2. Step 2: Understand impact on semester count

    Since multiple courses with zero indegree can be taken in parallel, processing one at a time inflates semester count incorrectly.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Correct BFS processes all zero indegree nodes per semester [OK]
Quick Trick: Process all zero indegree courses per semester, not one [OK]
Common Mistakes:
MISTAKES
  • Incrementing semester inside inner loop
  • Not processing all available courses in one semester
  • Incorrect indegree updates causing infinite loops
Trap Explanation:
PITFALL
  • Processing one course per semester looks simpler but breaks parallelism assumption, inflating semesters.
Interviewer Note:
CONTEXT
  • Tests if candidate spots subtle off-by-one in BFS level processing.
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