Bird
Raised Fist0

Given the memo array after DFS with memoization: [True, False, True, None, True], which of the following graphs could produce this memo state for nodes 0 to 4?

hard🔄 Reverse Engineer Q9 of Q15
Topological Sort - Find Eventual Safe States
Given the memo array after DFS with memoization: [True, False, True, None, True], which of the following graphs could produce this memo state for nodes 0 to 4?
A[[1],[2],[3],[],[0]]
B[[1],[2],[3],[],[]]
C[[1],[0],[3],[4],[]]
D[[],[0],[1],[2],[3]]
Step-by-Step Solution
Solution:
  1. Step 1: Interpret memo values

    True means safe, False unsafe, None unvisited. Node 1 is unsafe, node 3 unvisited.
  2. Step 2: Match graph structure

    Graph A has edges [[1],[2],[3],[],[]], node 1 leads to node 2 (safe), node 3 is terminal (safe), matching memo.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Memo matches safe/unsafe states in graph A [OK]
Quick Trick: Match memo True/False to reachable terminal nodes [OK]
Common Mistakes:
MISTAKES
  • Ignoring None as unvisited
  • Misinterpreting safe vs unsafe
Trap Explanation:
PITFALL
  • Candidates confuse memo meanings or fail to reason backward from memo to graph.
Interviewer Note:
CONTEXT
  • Tests deep understanding of DFS memoization state and graph structure.
Master "Find Eventual Safe States" 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