Bird
Raised Fist0

Given the following input words: ["wrt", "wrf", "er", "ett", "rftt"], what is the output order of characters returned by the optimal alien dictionary solution using BFS topological sort?

easy🧾 Code Trace Q3 of Q15
Topological Sort - Alien Dictionary (Infer Character Order)
Given the following input words: ["wrt", "wrf", "er", "ett", "rftt"], what is the output order of characters returned by the optimal alien dictionary solution using BFS topological sort?
A"wertf"
B"wert"
C"wretf"
D"wrtef"
Step-by-Step Solution
Solution:
  1. Step 1: Build graph edges from adjacent words

    Edges: w->e, e->r, r->t, t->f based on first differing characters.
  2. Step 2: Perform BFS topological sort

    Start with nodes with zero in-degree: w; order: w, e, r, t, f.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Order matches graph edges and BFS traversal [OK]
Quick Trick: Build graph from first differing chars [OK]
Common Mistakes:
MISTAKES
  • Mixing order of characters in output
Trap Explanation:
PITFALL
  • Candidates often confuse order of insertion or miss edges, producing incorrect sequences.
Interviewer Note:
CONTEXT
  • Tests candidate's ability to trace BFS topological sort on typical input
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