Skip to main content

24. Alien Dictionary

hardAsked at Palantir

Given a list of words sorted lexicographically by an alien language, derive the character order. Palantir asks this because it's the textbook example of inferring a partial order from observed pairs — exactly what their ontology system does when reconciling type hierarchies from disparate source systems during entity resolution.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir FDE on-site — frame: 'infer ordering from pairwise constraints'.
  • Blind (2025-11)— Reported with strict edge-case grading (prefix words).

Problem

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language. If this claim is incorrect, return an empty string. Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order. If there are multiple valid orders, return any of them.

Constraints

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

Examples

Example 1

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

Example 2

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

Example 3

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

Explanation: Cycle: z<x and x<z is contradictory.

Example 4

Input
words = ['abc','ab']
Output
''

Explanation: Prefix is not allowed before its parent.

Approaches

1. Brute force permutations

Generate every permutation of distinct letters; check if the input is sorted under that order.

Time
O(k! * total_chars)
Space
O(k)
// O(k!) — for 26 letters this is 4 * 10^26 ops. Skipped — Palantir will reject on sight.
function alienOrder(words) {
  throw new Error('TLE');
}

Tradeoff: Factorial — completely impractical. Mention only to motivate the graph approach.

2. Build precedence graph + Kahn's topo sort

For each adjacent pair, find the first differing character — that's a precedence edge. Validate prefix rule. Run Kahn's; if cycle, return ''.

Time
O(total_chars)
Space
O(k + edges)
function alienOrder(words) {
  const graph = new Map();
  const inDegree = new Map();
  for (const w of words) for (const c of w) {
    if (!graph.has(c)) { graph.set(c, new Set()); inDegree.set(c, 0); }
  }
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i], b = words[i+1];
    if (a.length > b.length && a.startsWith(b)) return '';
    for (let j = 0; j < Math.min(a.length, b.length); j++) {
      if (a[j] !== b[j]) {
        if (!graph.get(a[j]).has(b[j])) {
          graph.get(a[j]).add(b[j]);
          inDegree.set(b[j], inDegree.get(b[j]) + 1);
        }
        break;
      }
    }
  }
  const queue = [];
  for (const [c, d] of inDegree) if (d === 0) queue.push(c);
  let out = '';
  while (queue.length) {
    const c = queue.shift();
    out += c;
    for (const next of graph.get(c)) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) queue.push(next);
    }
  }
  return out.length === inDegree.size ? out : '';
}

Tradeoff: Linear in total input chars — the canonical Palantir answer. The two non-obvious pieces: (1) the prefix-violation check, (2) only one precedence edge per adjacent pair, since later differing chars give no information.

Palantir-specific tips

Palantir's hard-tier grading on this question splits three ways: (1) do you derive the right precedence edges from adjacent pairs (one edge per pair), (2) do you catch the prefix violation ('abc' before 'ab' is invalid), and (3) do you handle the cycle case correctly. State all three up front. Bonus signal: connect to entity resolution — inferring a type hierarchy from pairwise 'X is a Y' assertions has the same shape, including the inconsistency detection.

Common mistakes

  • Adding edges for ALL differing chars in an adjacent pair — only the first differing char carries information. The rest are unconstrained.
  • Forgetting the prefix-violation edge case ('abc' followed by 'ab' is invalid input — return '').
  • Adding duplicate edges to the graph without dedup, inflating in-degree and missing valid characters in the output.

Follow-up questions

An interviewer at Palantir may pivot to one of these next:

  • What if multiple valid orders exist — return them all (much harder).
  • Verifying alien dictionary (LC 953) — easier variant, order given.
  • Online version: words arrive in a stream, maintain the order incrementally.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why only ONE edge per adjacent pair?

Because once two words differ at position k, positions k+1 onwards give you no info — those characters could be in any order. Adding extra edges introduces false constraints.

How do I detect the prefix violation?

When words[i] starts with words[i+1] AND words[i].length > words[i+1].length, the input is contradictory — return ''. The shorter word must come first lexicographically.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →