Bird
Raised Fist0

Given the following code snippet implementing topological sort positions, what is the final value of the pos array after processing conditions = [[1,2],[1,3],[3,4]] with n=4?

easy🧾 Code Trace Q12 of Q15
Topological Sort - Build a Matrix With Conditions
Given the following code snippet implementing topological sort positions, what is the final value of the pos array after processing conditions = [[1,2],[1,3],[3,4]] with n=4?
A[0, 0, 1, 2, 3]
B[0, 0, 2, 1, 3]
C[0, 0, 1, 3, 2]
D[0, 1, 2, 3, 0]
Step-by-Step Solution
  1. Step 1: Initialize graph and in-degree arrays

    Edges: 1->2, 1->3, 3->4; in_degree: [0,0,1,1,1]
  2. Step 2: Process queue and assign positions

    Queue starts with node 1 (in_degree 0). Assign pos[1]=0. Decrement in_degree of 2 and 3 to 0, enqueue both. Next, dequeue 2 (pos[2]=1), then dequeue 3 (pos[3]=2), decrement in_degree of 4 to 0, enqueue 4, assign pos[4]=3.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Positions reflect valid topological order [OK]
Quick Trick: Track in-degree and queue order carefully [OK]
Common Mistakes:
MISTAKES
  • Swapping positions of nodes 2 and 3
  • Off-by-one indexing in pos array
Trap Explanation:
PITFALL
  • Multiple nodes with zero in-degree can be dequeued in any order; common mistake is mixing their positions.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute topological sort and track positions precisely.
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