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.
Quick 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 ''