DSA interview question

Alien Dictionary

Hard · Data structures · Topics: graph, bfs, topological sort, string

The problem

Archaeologists found a dictionary from an alien civilisation: a list of words sorted lexicographically by the aliens' alphabet, whose letter order is unknown. Recover an order of the letters that's consistent with the list, or return "" if none exists. Each pair of adjacent words reveals at most one fact: at their first differing position, the first word's letter comes before the second's. Those facts form a directed graph, and any topological order of it is a valid alphabet. Using a min-heap picks the alphabetically smallest valid order, so the answer is unique.

Example: ["wrt", "wrf", "er", "ett", "rftt"] → "wertf".

Function signature

string alienOrder(const vector<string>& words);  // lexicographically smallest valid order, or ""

Test cases

Input	Output	Explanation
`["wrt","wrf","er","ett","rftt"]`	`"wertf"`	t<f, w<e, r<t, e<r
`["z","x"]`	`"zx"`
`["ab","adc"]`	`"abcd"`	Only b<d is known; c is free
`["z","x","z"]`	`""`	z<x and x<z: a cycle
`["abc","ab"]`	`""`	A longer word can't come before its own prefix

(Confirm: letters are lowercase; the output contains exactly the letters that appear; when several orders fit, the lexicographically smallest is returned here.)

How interviewers phrase it

"Given a list of words sorted in an alien language, derive the order of letters in that language" (LeetCode 269; GeeksforGeeks "Alien Dictionary" gives K letters).

Clarifying questions to ask

Should letters with no constraints be included? (Yes, every letter that appears.)
What if the input is inconsistent? (Return "".)
Which order if several fit? (Any; this version returns the smallest.)

Follow-ups to expect

"Why only adjacent pairs?"
"Why only the first differing letter?"
"What about the prefix case?"
"How is a cycle detected?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview