Bird
Raised Fist0

Given org = [1, 2, 3] and seqs = [[1, 2], [1, 3]], what is the final return value of sequenceReconstruction(org, seqs)?

easy🧾 Code Trace Q12 of Q15
Topological Sort - Sequence Reconstruction (Unique Topo Order)
Consider the following Python code implementing sequence reconstruction using DFS postorder topological sort. Given org = [1, 2, 3] and seqs = [[1, 2], [1, 3]], what is the final return value of sequenceReconstruction(org, seqs)?
Atrue
BRaises an exception due to cycle
Cfalse
DReturns null
Step-by-Step Solution
  1. Step 1: Build graph and check nodes

    Nodes are {1,2,3}, matching org. Edges: 1->2 and 1->3.
  2. Step 2: Perform DFS and check uniqueness

    DFS postorder yields stack with nodes in order [2,3,1] reversed to [1,3,2]. This does not match org [1,2,3], so return false.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Multiple valid topological orders exist, so uniqueness fails [OK]
Quick Trick: Multiple valid orders -> false [OK]
Common Mistakes:
MISTAKES
  • Assuming any topo order matching partial orders is unique
  • Forgetting to reverse stack before comparison
Trap Explanation:
PITFALL
  • Stack reversal is critical; ignoring it leads to wrong true answer.
Interviewer Note:
CONTEXT
  • Tests candidate's ability to trace DFS topo sort and uniqueness check carefully.
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