Bird
Raised Fist0

Given the following code snippet implementing DFS postorder topological sort for sequence reconstruction, what is the return value for org = [1,2,3] and seqs = [[1,2],[1,3]]?

easy🧾 Code Trace Q3 of Q15
Topological Sort - Sequence Reconstruction (Unique Topo Order)
Given the following code snippet implementing DFS postorder topological sort for sequence reconstruction, what is the return value for org = [1,2,3] and seqs = [[1,2],[1,3]]?
ATrue, because the unique sequence matches org
BFalse, because multiple valid sequences exist
CFalse, because seqs is missing elements
DTrue, because any topological order is accepted
Step-by-Step Solution
Solution:
  1. Step 1: Build graph and analyze edges

    Edges: 1->2 and 1->3. Both 2 and 3 come after 1, but no order between 2 and 3.
  2. Step 2: Check uniqueness of topological order

    Possible orders: [1,2,3] and [1,3,2]. Since multiple valid orders exist, unique reconstruction fails.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Multiple valid sequences -> return False [OK]
Quick Trick: Multiple valid topological orders -> False [OK]
Common Mistakes:
MISTAKES
  • Assuming any topological order means unique reconstruction
Trap Explanation:
PITFALL
  • Candidates confuse existence of a topological order with uniqueness of that order.
Interviewer Note:
CONTEXT
  • Tests ability to trace DFS topological sort and uniqueness logic.
Master "Sequence Reconstruction (Unique Topo 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