Skip to main content

24. Alien Dictionary

hardAsked at Roblox

Derive character ordering rules from a sorted alien-language word list using topological sort — Roblox applies the same dependency-extraction technique to infer asset-load ordering from observed streaming sequences across game worlds.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given a list of strings words sorted lexicographically in an alien language. Derive the order of letters in this language and return it as a string. If the order is invalid (cycle detected), return an empty string. If multiple valid orderings exist, return any. All lowercase letters not appearing in the input may be omitted from the output.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters
  • words is sorted in the alien language's lexicographic order

Examples

Example 1

Input
words = ["wrt","wrf","er","ett","rftt"]
Output
"wertf"

Explanation: Derived edges: t->f, w->e, r->t, e->r. Topological order: w e r t f.

Example 2

Input
words = ["z","x"]
Output
"zx"

Example 3

Input
words = ["z","x","z"]
Output
""

Explanation: Cycle detected — invalid.

Approaches

1. Brute force — adjacency list + DFS cycle check

Build a directed graph from adjacent word pairs, then run DFS with three-color marking to detect cycles and collect the post-order traversal as the character ordering.

Time
O(C) where C = total characters in all words
Space
O(1) since at most 26 characters
function alienOrder(words) {
  const adj = new Map();
  for (const w of words) for (const c of w) if (!adj.has(c)) adj.set(c, new Set());

  for (let i = 0; i < words.length - 1; i++) {
    const [w1, w2] = [words[i], words[i + 1]];
    const minLen = Math.min(w1.length, w2.length);
    if (w1.length > w2.length && w1.startsWith(w2)) return '';
    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) { adj.get(w1[j]).add(w2[j]); break; }
    }
  }

  const UNVISITED = 0, VISITING = 1, VISITED = 2;
  const state = new Map([...adj.keys()].map(c => [c, UNVISITED]));
  const result = [];

  function dfs(c) {
    if (state.get(c) === VISITING) return false;
    if (state.get(c) === VISITED) return true;
    state.set(c, VISITING);
    for (const next of adj.get(c)) {
      if (!dfs(next)) return false;
    }
    state.set(c, VISITED);
    result.push(c);
    return true;
  }

  for (const c of adj.keys()) {
    if (!dfs(c)) return '';
  }
  return result.reverse().join('');
}

Tradeoff:

2. Optimal — Kahn's BFS topological sort

Build the graph and compute in-degrees from adjacent word comparisons. Enqueue zero-in-degree characters and peel layers with BFS. If processed count < unique character count, a cycle exists.

Time
O(C)
Space
O(1) for ≤26 chars
function alienOrder(words) {
  const adj = new Map();
  const inDegree = new Map();
  for (const w of words) for (const c of w) { adj.set(c, adj.get(c) || new Set()); inDegree.set(c, inDegree.get(c) || 0); }

  for (let i = 0; i < words.length - 1; i++) {
    const [w1, w2] = [words[i], words[i + 1]];
    if (w1.length > w2.length && w1.startsWith(w2)) return '';
    for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
      if (w1[j] !== w2[j]) {
        if (!adj.get(w1[j]).has(w2[j])) {
          adj.get(w1[j]).add(w2[j]);
          inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
        }
        break;
      }
    }
  }

  const queue = [...inDegree.entries()].filter(([,d]) => d === 0).map(([c]) => c);
  const result = [];

  while (queue.length) {
    const c = queue.shift();
    result.push(c);
    for (const next of adj.get(c)) {
      const d = inDegree.get(next) - 1;
      inDegree.set(next, d);
      if (d === 0) queue.push(next);
    }
  }

  return result.length === adj.size ? result.join('') : '';
}

Tradeoff:

Roblox-specific tips

Roblox asks this at the senior level because extracting ordering constraints from observations is a real systems skill — their engine has to infer which Lua modules or assets must load before others based on observed dependency signals. Pay attention to the invalid-input edge case: a prefix word appearing after a longer word that starts with it (e.g., ["ab", "a"]) is immediately invalid. Catching that case earns points with Roblox interviewers who care about defensive engineering.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Alien Dictionary and other Roblox interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →