Bird
Raised Fist0

Given the final topological order "wertf" and the graph edges: w->e, e->r, r->t, t->f, which of the following could be the original input words list?

hard🔄 Reverse Engineer Q9 of Q15
Topological Sort - Alien Dictionary (Infer Character Order)
Given the final topological order "wertf" and the graph edges: w->e, e->r, r->t, t->f, which of the following could be the original input words list?
A["wrt", "wrf", "er", "ett", "rftt"]
B["wertf", "wert"]
C["w", "e", "r", "t", "f"]
D["wrtf", "wert"]
Step-by-Step Solution
Solution:
  1. Step 1: Match edges to first differing characters in adjacent words

    Edges w->e, e->r, r->t, t->f correspond to pairs in ["wrt", "wrf", "er", "ett", "rftt"].
  2. Step 2: Verify order consistency

    Order "wertf" respects all edges and matches known example input.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Edges and order consistent with input words [OK]
Quick Trick: Edges correspond to first differing chars in adjacent words [OK]
Common Mistakes:
MISTAKES
  • Choosing inputs that don't produce given edges
Trap Explanation:
PITFALL
  • Candidates often pick inputs ignoring edge constraints, leading to inconsistent orders.
Interviewer Note:
CONTEXT
  • Tests deep understanding of graph construction from input and order inference
Master "Alien Dictionary (Infer Character 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