Skip to main content

23. Alien Dictionary

hardAsked at CircleCI

Derive character ordering from a sorted alien word list using topological sort — the same DAG-ordering logic CircleCI uses to resolve job execution sequences from dependency declarations.

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

Problem

Given a list of words sorted lexicographically in an alien language, derive the character ordering rules and return any valid ordering of characters. Return an empty string if no valid ordering exists (cycle detected).

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters

Examples

Example 1

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

Example 2

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

Approaches

1. Topological sort (Kahn's BFS)

Extract ordering edges by comparing adjacent word pairs character by character, build a DAG, then apply Kahn's BFS to produce topological order.

Time
O(C) where C = total characters
Space
O(1) — at most 26 nodes
function alienOrder(words) {
  const adj = {};
  const indegree = {};
  for (const w of words) for (const c of w) { adj[c] = adj[c] || new Set(); indegree[c] = indegree[c] ?? 0; }
  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]) { if (!adj[w1[j]].has(w2[j])) { adj[w1[j]].add(w2[j]); indegree[w2[j]]++; } break; }
    }
  }
  const queue = Object.keys(indegree).filter(c => indegree[c] === 0);
  let result = '';
  while (queue.length) {
    const c = queue.shift(); result += c;
    for (const nb of adj[c]) { if (--indegree[nb] === 0) queue.push(nb); }
  }
  return result.length === Object.keys(indegree).length ? result : '';
}

Tradeoff:

2. DFS post-order topological sort

Run DFS over the character graph, appending to result in post-order and reversing; detect back edges (cycles) using a three-color scheme.

Time
O(C)
Space
O(1)
function alienOrder(words) {
  const adj = {};
  for (const w of words) for (const c of w) adj[c] = adj[c] || new Set();
  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]) { adj[w1[j]].add(w2[j]); break; }
    }
  }
  const state = {}, result = [];
  function dfs(c) {
    if (state[c] === 1) return false;
    if (state[c] === 2) return true;
    state[c] = 1;
    for (const nb of adj[c]) if (!dfs(nb)) return false;
    state[c] = 2; result.push(c); return true;
  }
  for (const c of Object.keys(adj)) if (!dfs(c)) return '';
  return result.reverse().join('');
}

Tradeoff:

CircleCI-specific tips

CircleCI interviewers use this to probe whether you can build a constraint graph from implicit rules — articulate the edge-extraction step from word comparisons clearly before writing any graph code.

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 CircleCI interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →