Alien Dictionary
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber
Problem
Given a sorted list of words in an alien language, find the order of characters in that language. This is a topological sort problem disguised as a string problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Meta | Hard | View all Meta questions → |
| Amazon | Hard | View all Amazon questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Apple | Hard | View all Apple questions → |
| Uber | Hard | View all Uber questions → |
How to Think About It
Compare adjacent words to find the first differing character. That gives an ordering constraint: char A comes before char B (edge from A to B in the graph).
Build a graph of character ordering. Each edge A→B means A must come before B in the alien alphabet.
Topological sort the graph to get the character order. Use Kahn's algorithm (BFS) with in-degree tracking.
Cycle detection: if the topological sort result has fewer characters than the total unique chars, a cycle exists (invalid input).
Visual walkthrough for ["wrt","wrf","er","ett","rftt"]:
Compare wrt vs wrf: first diff at index 2, t→f (t before f)
Compare wrf vs er: first diff at index 0, w→e (w before e)
Compare er vs ett: first diff at index 1, r→t (r before t)
Compare ett vs rftt: first diff at index 0, e→r (e before r)
Edges: t→f, w→e, r→t, e→r
Graph: w→e→r→t→f
Topological sort: w, e, r, t, f
Edge cases: single word (any order of its chars), invalid input where a longer word comes before its prefix.
Optimal Approach
Step 1: Build adjacency list from adjacent word comparisons. Find first differing char between each pair.
Step 2: Compute in-degrees for all characters.
Step 3: Kahn's algorithm — start with chars that have in-degree 0. For each, add to result, decrement in-degrees of neighbors.
Step 4: If result length < total unique chars, a cycle exists — return "".
Time: O(C) where C is total characters across all words. Space: O(1) — at most 26 nodes.
What Trips People Up in Real Interviews
Getting the edge direction wrong. If word1 comes before word2 and they differ at position i, the edge is word1[i] → word2[i] (word1[i] comes first in the alphabet).
Not detecting cycles. If the topological sort result is shorter than the number of unique characters, a cycle exists — return empty string.
Forgetting that a longer word coming before its prefix is invalid. If "abc" comes before "ab", that's impossible — return empty.
Not handling single-word input. With one word, any ordering of its characters is valid.
Adding edges for every differing character instead of just the first one. Only the FIRST differing character between adjacent words gives a reliable ordering constraint. Subsequent differences don't.
Solution Code
from collections import deque
def alienOrder(words):
adj = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return ""
for j in range(min_len):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
break
in_degree = {c: 0 for c in adj}
for c in adj:
for neighbor in adj[c]:
in_degree[neighbor] += 1
q = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while q:
c = q.popleft()
result.append(c)
for neighbor in adj[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
q.append(neighbor)
return "".join(result) if len(result) == len(adj) else ""Frequently Asked Questions
What is the Alien Dictionary problem?
Given a sorted list of words in an alien language, find the order of characters in that language. This is a topological sort problem disguised as a string problem.
How do you solve Alien Dictionary?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Alien Dictionary?
Alien Dictionary is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a hard difficulty problem.
What are common mistakes on Alien Dictionary?
- Getting the edge direction wrong. If word1 comes before word2 and they differ at position i, the edge is `word1[i]` → `word2[i]` (`word1[i]` comes first in the alphabet).
- Not detecting cycles. If the topological sort result is shorter than the number of unique characters, a cycle exists — return empty string.
- Forgetting that a longer word coming before its prefix is invalid. If "abc" comes before "ab", that's impossible — return empty.
- Not handling single-word input. With one word, any ordering of its characters is valid.
- Adding edges for every differing character instead of just the first one. Only the FIRST differing character between adjacent words gives a reliable ordering constraint. Subsequent differences don't.