Bird
Raised Fist0

```python from collections import deque, defaultdict def findOrder(numCourses, prerequisites): graph = defaultdict(list) in_degree = [0] * numCourses for dest, src in prerequisites: graph[src].append(dest) in_degree[dest] += 1 queue = deque([i for i in range(numCourses) if in_degree[i] == 0]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) if len(order) == numCourses: return order else: return [] ``` Which of the following is the most critical bug if the algorithm misbehaves?

medium🐛 Buggy Code Q7 of Q15
Topological Sort - Course Schedule II (Topological Order)
In the following snippet of Kahn's Algorithm, which mistake can cause the algorithm to fail or loop infinitely? ```python from collections import deque, defaultdict def findOrder(numCourses, prerequisites): graph = defaultdict(list) in_degree = [0] * numCourses for dest, src in prerequisites: graph[src].append(dest) in_degree[dest] += 1 queue = deque([i for i in range(numCourses) if in_degree[i] == 0]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) if len(order) == numCourses: return order else: return [] ``` Which of the following is the most critical bug if the algorithm misbehaves?
ANot updating in-degree after removing a node
BReturning order without checking if all courses are included
CAppending nodes to order before processing neighbors
DIncorrectly initializing the queue with nodes having zero in-degree
Step-by-Step Solution
Solution:
  1. Step 1: Understand queue initialization

    The queue must start with all nodes having zero in-degree.
  2. Step 2: Impact of incorrect initialization

    If nodes with non-zero in-degree are included or zero in-degree nodes missed, the algorithm may skip nodes or loop infinitely.
  3. Step 3: Other options analysis

    Updating in-degree is done correctly; appending order before neighbors is valid; final length check is present.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Queue must start with zero in-degree nodes [OK]
Quick Trick: Queue must start with all zero in-degree nodes [OK]
Common Mistakes:
MISTAKES
  • Starting queue with wrong nodes
  • Not decrementing in-degree properly
  • Skipping final length check
Trap Explanation:
PITFALL
  • Incorrect queue initialization can cause skipping or infinite loops, unlike other options.
Interviewer Note:
CONTEXT
  • Tests debugging skills and understanding of Kahn's Algorithm initialization.
Master "Course Schedule II (Topological Order)" 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