Bird
Raised Fist0

In the following topological sort code snippet, which line is most likely causing incorrect position assignments due to improper in-degree updates?

medium🐞 Bug Identification Q7 of Q15
Topological Sort - Build a Matrix With Conditions
In the following topological sort code snippet, which line is most likely causing incorrect position assignments due to improper in-degree updates?
1: for each node u in graph:
2:   if inDegree[u] == 0:
3:     queue.push(u)
4: while queue not empty:
5:   node = queue.pop()
6:   pos[node] = currentPosition++
7:   for each neighbor v of node:
8:     inDegree[v] -= 1
9:     if inDegree[v] == 0:
10:       queue.push(v)
ALine 6: Assigning position before processing neighbors
BLine 9: Checking in-degree after decrement instead of before
CLine 3: Initial queue push missing nodes with zero in-degree
DLine 8: Decrementing in-degree without checking if already zero
Step-by-Step Solution
Solution:
  1. Step 1: Understand In-degree Updates

    In-degree must be decremented exactly once per edge and never go below zero.
  2. Step 2: Identify Bug

    Line 8 decrements in-degree without ensuring it is positive, potentially causing negative values and incorrect queue pushes.
  3. Step 3: Correct Approach

    Ensure in-degree is positive before decrement or guard against multiple decrements to prevent negative values.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    In-degree must never become negative [OK]
Quick Trick: In-degree must not be decremented below zero [OK]
Common Mistakes:
MISTAKES
  • Assuming position assignment order causes bugs
  • Ignoring possibility of multiple decrements on same edge
  • Misreading queue initialization logic
Trap Explanation:
PITFALL
  • Decrementing in-degree blindly can cause invalid negative values
Interviewer Note:
CONTEXT
  • Tests ability to spot subtle bugs in graph traversal code
Master "Build a Matrix With Conditions" 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