Bird
Raised Fist0

Given the memo dictionary after running DFS with memoization on a DAG: {3: [[3]], 1: [[1,3]], 2: [[2,3]], 0: [[0,1,3],[0,2,3]]}, what is the original graph's adjacency list?

hard🔄 Reverse Engineer Q9 of Q15
Topological Sort - All Paths From Source to Target (DAG)
Given the memo dictionary after running DFS with memoization on a DAG: {3: [[3]], 1: [[1,3]], 2: [[2,3]], 0: [[0,1,3],[0,2,3]]}, what is the original graph's adjacency list?
A[[1,2],[3],[1],[]]
B[[1,2],[3],[3],[]]
C[[2],[3],[3],[]]
D[[1],[2],[3],[]]
Step-by-Step Solution
Solution:
  1. Step 1: Analyze memo entries

    Node 3 leads to [[3]] -> node 3 is target with no neighbors.
  2. Step 2: Check neighbors for nodes 1 and 2

    Both 1 and 2 lead to paths ending with 3, so neighbors of 1 and 2 include 3.
  3. Step 3: Node 0 has paths [0,1,3] and [0,2,3], so neighbors are 1 and 2.

    Thus, graph is [[1,2],[3],[3],[]].
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Memo matches adjacency list neighbors [OK]
Quick Trick: Memo paths reveal adjacency neighbors [OK]
Common Mistakes:
MISTAKES
  • Confusing path nodes with neighbors
  • Ignoring target node with empty neighbors
Trap Explanation:
PITFALL
  • Candidates often misinterpret memo paths as direct neighbors instead of full paths.
Interviewer Note:
CONTEXT
  • Tests deep understanding of memoization state and graph reconstruction.
Master "All Paths From Source to Target (DAG)" 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