Alien Dictionary (Topological Order)
Given a sorted list of words from an alien language, derive a valid character order. Return '' if invalid (cycle or contradiction).
Answers use simple, clear English.
Audio N/AQuick interview answer
Compare consecutive words to extract precedence edges between first differing letters. Also detect length prefix violations (apple before app). Topologically sort characters; cycle ⇒ invalid.
Detailed answer
Compare consecutive words to extract precedence edges between first differing letters. Also detect length prefix violations (apple before app). Topologically sort characters; cycle ⇒ invalid. Classic hard graph problem at senior interviews.
Full explanation
Classic hard graph problem at senior interviews.
Real example & use case
Localizing a CMS where custom alphabet order must be inferred from editor-sorted samples.
Pros & cons
Pros: reduces to topo sort. Cons: edge extraction and prefix rules are easy to miss.
Code example
from collections import defaultdict, deque
def alien_order(words: list[str]) -> str:
nodes = set(''.join(words))
g = defaultdict(set)
indeg = {c: 0 for c in nodes}
for a, b in zip(words, words[1:]):
if len(a) > len(b) and a.startswith(b):
return ''
for ca, cb in zip(a, b):
if ca != cb:
if cb not in g[ca]:
g[ca].add(cb)
indeg[cb] += 1
break
q = deque([c for c, d in indeg.items() if d == 0])
order = []
while q:
u = q.popleft(); order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return ''.join(order) if len(order) == len(nodes) else ''Practice code · python (view only · no execution)
from collections import defaultdict, deque
def alien_order(words: list[str]) -> str:
nodes = set(''.join(words))
g = defaultdict(set)
indeg = {c: 0 for c in nodes}
for a, b in zip(words, words[1:]):
if len(a) > len(b) and a.startswith(b):
return ''
for ca, cb in zip(a, b):
if ca != cb:
if cb not in g[ca]:
g[ca].add(cb)
indeg[cb] += 1
break
q = deque([c for c, d in indeg.items() if d == 0])
order = []
while q:
u = q.popleft(); order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return ''.join(order) if len(order) == len(nodes) else ''