Prompt and Applicable Context
Given an array words of nonempty lowercase ASCII strings, assume the array is claimed to be sorted by an unknown alphabet. Return any ordering that contains every distinct character in the input exactly once and makes the word list sorted. Return an empty string when no such ordering exists. If several alphabets work, any one is acceptable.
For the interview version, assume at most 10,000 words and at most 100,000 characters in total. These are exercise constraints, not limits from a particular platform. For ["wrt", "wrf", "er", "ett", "rftt"], one answer is "wertf". The list ["abc", "ab"] is impossible because a longer word precedes its own prefix. The list ["z", "x", "z"] is impossible because it implies both z < x and x < z.
The hard part comes before topological sort. The input supplies sorted words; graph edges must be inferred. A correct solution must infer exactly the constraints justified by lexicographic comparison, retain characters that have no edges, and distinguish an invalid prefix from a directed cycle.
What the Interviewer Evaluates
The first signal is whether the candidate derives an edge from the first differing character of two adjacent words. If "wrt" appears before "wrf", the comparison proves t < f. Characters after that first difference reveal nothing about this pair because lexicographic comparison has already been decided.
The second signal is prefix reasoning. When all compared characters match, the shorter word must come first. "ab" before "abc" adds no edge and remains valid; "abc" before "ab" contradicts every possible alphabet. Topological sorting alone cannot discover this contradiction because it creates no edge.
The third signal is complete graph construction. Every observed character needs a node, including an isolated character from a single-word input. Repeated evidence for the same edge must not increment indegree twice. A set per source node keeps adjacency and indegree consistent.
The final signals are proof and validation. Kahn's algorithm returns a complete order only when it removes every node. A shorter output proves a cycle remains. Multiple zero-indegree choices mean the evidence does not determine one unique alphabet; that is valid under the base contract and should not be mislabeled as an error.
Questions to Clarify Before Answering
- Does the input include every character in the alphabet? This answer orders every character observed
in the words. It cannot invent or place unseen characters without an external alphabet definition.
- Is any valid order acceptable? The base problem accepts any. Requiring the smallest result under the
host language's character order needs a min-heap and changes the complexity.
- How should impossibility be represented? This contract uses an empty string for both an invalid
prefix and a cycle. A production API may return a structured reason and witness.
- What is a character? The base input contains lowercase ASCII letters. Unicode code points or grapheme
clusters require a tokenization contract before graph construction.
- May words repeat? Yes. Equal adjacent words add no constraint. They do not make the dictionary invalid.
- Must the alphabet be unique? No. A follow-up can detect uniqueness by checking the number of available
zero-indegree nodes at every step.
- Can the input be empty? This version requires at least one nonempty word. If empty input is allowed,
confirm whether the expected result is an empty alphabet or an invalid request.
30-Second Answer Framework
“I will create a graph node for every distinct character. For each adjacent word pair, I scan to the first difference; that gives one directed edge from the earlier word's character to the later word's character. If there is no difference and the earlier word is longer, the prefix order is impossible, so I return an empty string. I deduplicate edges while maintaining indegrees, then run Kahn's topological sort from all zero-indegree characters. If I process every node, the result respects every inferred comparison; if I process fewer nodes, a cycle makes the dictionary inconsistent. The total time is linear in the input characters plus the graph, and multiple valid topological orders are acceptable.”
Step-by-Step Deep Dive
Let C be the total number of characters across all words, U the number of distinct characters, and E the number of distinct precedence edges. Initialize graph[ch] as a set and indegree[ch] as zero for every character encountered. This initialization is necessary before comparing words: a character can be valid and unconstrained, so edge endpoints alone do not define the node set.
Compare only adjacent words. Adjacent comparisons are sufficient because proving every neighboring pair is ordered proves the whole list is ordered by transitivity. They also avoid the quadratic number of word-pair comparisons. For a pair first and second, inspect matching positions up to the shorter length:
- At the first mismatch
first[i] != second[i], addfirst[i] -> second[i]and stop comparing that pair. - If every shared position matches and
firstis longer, return an empty string. - If every shared position matches and
firstis no longer, add no edge.
Only a newly inserted edge increments the destination's indegree. Suppose both "za" < "zb" and "ca" < "cb" imply a -> b. Counting that edge twice would leave b with a positive indegree after a is removed and falsely report a cycle.
Kahn's algorithm puts every zero-indegree character into a queue. Its invariant is: for every unprocessed character, indegree equals the number of incoming edges from other unprocessed characters; the queue contains exactly the characters with no such predecessor. Removing a queued character is safe. Decrementing each outgoing neighbor models removal of those edges, and a neighbor enters the queue when its last unmet predecessor disappears.
from collections import deque
def alien_order(words: list[str]) -> str:
graph = {char: set() for word in words for char in word}
indegree = {char: 0 for char in graph}
for first, second in zip(words, words[1:]):
limit = min(len(first), len(second))
for index in range(limit):
before = first[index]
after = second[index]
if before == after:
continue
if after not in graph[before]:
graph[before].add(after)
indegree[after] += 1
break
else:
if len(first) > len(second):
return ""
ready = deque(
char for char, degree in indegree.items() if degree == 0
)
order: list[str] = []
while ready:
char = ready.popleft()
order.append(char)
for neighbor in graph[char]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
ready.append(neighbor)
return "".join(order) if len(order) == len(indegree) else ""The proof has two layers. First, graph extraction is sound: every edge comes from the first mismatch of an adjacent pair, so every valid alphabet must respect it. The prefix check removes the only adjacent case in which no mismatch exists but ordering is impossible. Second, topological sorting is sound: the queue invariant ensures every output character appears after all inferred predecessors. Therefore each adjacent word pair is ordered, which makes the full list ordered.
If the algorithm outputs fewer than U characters, every remaining node has positive indegree. Starting from any remaining node and repeatedly following an incoming edge must revisit a node in a finite graph; the repeated segment is a directed cycle. No linear alphabet can satisfy that cycle. Conversely, an acyclic graph always has a zero-indegree node, so Kahn's algorithm eventually removes all nodes and returns a valid order.
Building all nodes and scanning adjacent words takes O(C). Each distinct node and edge is processed once by Kahn's algorithm, so total time is O(C + U + E) and extra space is O(U + E). With lowercase ASCII, U is at most 26, but retaining the symbolic bound makes the reasoning reusable.
Validation should check properties when multiple answers are possible. A nonempty result must contain the distinct input characters exactly once. For every adjacent pair, compare it using the returned rank map and confirm it is ordered; separately confirm no longer word precedes its prefix. Test one word, repeated words, isolated characters, duplicate edge evidence, a valid prefix, an invalid prefix, a cycle, a chain, and a graph with several zero-indegree nodes.
DFS with white, gray, and black states is a correct alternative. It detects cycles through an edge to a gray node and reverses postorder for the result. Kahn's algorithm makes ambiguity visible through the ready set and avoids recursion depth concerns, so it is the clearer recommendation for this contract.
High-Quality Sample Answer
“I first need to infer a partial order from the sorted words. I create a node for every character, including characters that never participate in an edge. For each neighboring pair, I scan until the first mismatch. If the pair is wrt and wrf, I add t -> f and stop because later positions cannot affect that comparison. If there is no mismatch and the first word is longer, such as abc before ab, the input is already inconsistent.
I store neighbors in sets so repeated evidence for one relation increments indegree only once. Then I run Kahn's algorithm: enqueue all zero-indegree characters, remove one into the answer, decrement its outgoing neighbors, and enqueue a neighbor when its indegree reaches zero. The invariant is that queued characters have no predecessor left among unprocessed characters, so every emitted character is safe.
If the output length equals the number of distinct characters, every inferred edge is respected. Those edges plus the prefix checks make every adjacent word pair ordered, so the entire list is ordered. If the length is shorter, the remaining graph contains a cycle and no alphabet works. The runtime is O(C + U + E) with O(U + E) space. I would test a longer word before its prefix, a two-edge cycle, duplicate evidence for one edge, a single word, and a case with several valid outputs; for the last case I would validate ordering properties instead of expecting one string.”
Common Mistakes
- Using every differing position in a word pair → later positions do not participate once the first
mismatch decides lexicographic order → add only the first-mismatch edge and stop.
- Running only topological sort →
"abc"before"ab"creates no edge and slips through → **check the
longer-before-prefix contradiction during pair comparison.**
- Creating nodes only when adding edges → isolated characters disappear from the answer → **initialize
a node for every observed character.**
- Incrementing indegree for duplicate edges → a valid node never reaches zero → **use an adjacency set
and increment only on first insertion.**
- Returning the partial result when the queue empties → cyclic constraints appear successful → **require
output length to equal the distinct-character count.**
- Demanding one fixed answer → valid partial orders can have several linear extensions → **test the
returned order against characters, edges, and word comparisons.**
- Comparing every word pair → work can become quadratic in the word count → **adjacent comparisons are
sufficient to establish sorted order.**
- Claiming ambiguity means invalid input → multiple alphabets can explain the same evidence → **return
any valid order unless uniqueness is part of the contract.**
Follow-Up Questions and Responses
Follow-up 1: How do you determine whether the alphabet is unique?
During Kahn's algorithm, inspect the ready set before each removal. If it ever contains more than one character, at least two choices can be swapped into different valid topological orders, so the evidence is ambiguous. If it always contains exactly one character and every node is processed, the order is unique. An empty ready set before completion still means a cycle.
Follow-up 2: How do you return the smallest valid result under normal character order?
Replace the queue with a min-heap keyed by the host language's character order. Choosing the smallest currently valid character produces the smallest linear extension by a greedy exchange argument. The time becomes O(C + E + U log U); state clearly that this tie-breaker is external to the alien alphabet.
Follow-up 3: How would you return a useful explanation for invalid input?
For a prefix contradiction, return the two adjacent words and their indices. For a cycle, run a three-color DFS on the remaining graph after Kahn stalls, keep parent pointers, and reconstruct the characters forming one back-edge cycle. A structured result can distinguish invalid_prefix, cycle, and valid without overloading the empty string.
Follow-up 4: Can you process the word list as a stream?
Keep the previous word, add nodes from each new word, and derive the one adjacent-pair constraint when the next word arrives. The graph and indegrees still need storage until the stream ends because later evidence can add predecessors or create a cycle. Run topological sort only after all words have been observed unless the source supplies a finalization boundary.
Follow-up 5: How would you enumerate every valid alphabet?
Backtrack over all current zero-indegree characters. Choose one, remove its outgoing edges, recurse, then restore the state. This enumerates only valid orders, but the output can approach U!; confirm a small alphabet or an output limit before implementing it.
Follow-up 6: What changes for Unicode words?
Define the comparison unit first. Code points do not always match user-perceived characters, and locale collation can treat normalized forms or multi-code-point sequences specially. Tokenize each word according to the stated alphabet symbols, normalize only if the contract requires it, then run the same graph algorithm over tokens. Without that contract, “character order” is underspecified.