Bird
Raised Fist0

Given the final position arrays pos_row = [0, 2, 1] and pos_col = [1, 0, 2] for elements 1, 2, 3 respectively, which of the following sets of conditions could have produced these positions?

hard🔄 Reverse Engineer Q9 of Q15
Topological Sort - Build a Matrix With Conditions
Given the final position arrays pos_row = [0, 2, 1] and pos_col = [1, 0, 2] for elements 1, 2, 3 respectively, which of the following sets of conditions could have produced these positions?
ArowConditions = [(1,2), (2,3)], colConditions = [(2,1), (1,3)]
BrowConditions = [(1,3), (3,2)], colConditions = [(2,1), (1,3)]
CrowConditions = [(1,3), (2,3)], colConditions = [(2,1), (3,1)]
DrowConditions = [(3,1), (2,1)], colConditions = [(1,2), (3,2)]
Step-by-Step Solution
Solution:
  1. Step 1: Analyze pos_row = [0, 2, 1]

    This means element 1 is before 3, and 3 is before 2 in row order, matching rowConditions = [(1,3), (3,2)].
  2. Step 2: Analyze pos_col = [1, 0, 2]

    This means element 2 is before 1, and 1 is before 3 in column order, matching colConditions = [(2,1), (1,3)].
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Conditions correctly produce the given position arrays [OK]
Quick Trick: Positions reflect partial order edges [OK]
Common Mistakes:
MISTAKES
  • Mixing row and column conditions
  • Misinterpreting position indices
Trap Explanation:
PITFALL
  • Candidates confuse which conditions produce which position arrays.
Interviewer Note:
CONTEXT
  • Tests deep understanding of how conditions map to positions.
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