Alien Dictionary — Google Topological Sort Interview Question

Problem Statement#

Given a list of words sorted lexicographically in an unknown alien alphabet, return any string that lists every distinct character in a valid order. Return an empty string if no valid order exists.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters
• The given ordering may be inconsistent or may contradict a prefix rule

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

Input:  words = ["abc","ab"]
Output: ""

Why This Problem Matters#

This is LeetCode 269 Alien Dictionary, marked premium and asked at Google more than at any other FAANG. Google interviewers like it because it forces three skills in one room: graph modelling, topological sorting, and edge-case handling for the prefix invalid case. Strong candidates spot the directed graph in the prompt within the first minute and weaker candidates get stuck thinking it is a string problem.

The Core Insight#

Adjacent word pairs in a sorted dictionary tell you exactly one ordering relationship — the first differing character. Compare every adjacent pair, find the first index where they differ, and add a directed edge from w1[j] to w2[j]. That edge means w1[j] comes before w2[j] in the alphabet.

Once you have the graph, Kahn's algorithm gives a topological order. Push every zero in-degree character into a queue, pop, append to output, and decrement neighbour in-degrees. If the output length matches the number of distinct characters, return it. Otherwise a cycle exists — return empty.

There is one tricky case. If w1 is longer than w2 and w2 is a prefix of w1, like "abc" then "ab", the input itself is invalid and you must return empty before building the graph.

Visual Dry Run#

Final order from Kahn BFS: w, e, r, t, f → "wertf".

Solution (Optimal)#

from collections import defaultdict, deque
 
class Solution:
    def alienOrder(self, words):
        adj = defaultdict(set)
        in_degree = {c: 0 for w in words for c in w}
 
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            for j in range(min_len):
                if w1[j] != w2[j]:
                    if w2[j] not in adj[w1[j]]:
                        adj[w1[j]].add(w2[j])
                        in_degree[w2[j]] += 1
                    break
 
        q = deque([c for c, d in in_degree.items() if d == 0])
        order = []
        while q:
            c = q.popleft()
            order.append(c)
            for nxt in adj[c]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    q.append(nxt)
 
        if len(order) != len(in_degree):
            return ""
        return "".join(order)

var alienOrder = function(words) {
    const adj = new Map(), inDeg = new Map();
    for (const w of words) {
        for (const c of w) {
            if (!inDeg.has(c)) { inDeg.set(c, 0); adj.set(c, new Set()); }
        }
    }
    for (let i = 0; i < words.length - 1; i++) {
        const w1 = words[i], w2 = words[i + 1];
        if (w1.length > w2.length && w1.startsWith(w2)) return "";
        const min = Math.min(w1.length, w2.length);
        for (let j = 0; j < min; j++) {
            if (w1[j] !== w2[j]) {
                if (!adj.get(w1[j]).has(w2[j])) {
                    adj.get(w1[j]).add(w2[j]);
                    inDeg.set(w2[j], inDeg.get(w2[j]) + 1);
                }
                break;
            }
        }
    }
    const q = [];
    for (const [c, d] of inDeg) if (d === 0) q.push(c);
    const out = [];
    while (q.length) {
        const c = q.shift();
        out.push(c);
        for (const nxt of adj.get(c)) {
            inDeg.set(nxt, inDeg.get(nxt) - 1);
            if (inDeg.get(nxt) === 0) q.push(nxt);
        }
    }
    return out.length === inDeg.size ? out.join("") : "";
};

Time: O(C) — C is total characters across all words; building edges and running Kahn are both linear in C Space: O(1) effectively — at most 26 nodes and 26 squared edges in the lowercase English case

Common Mistakes#

• Forgetting the prefix-invalid check, which causes wrong answers on inputs like ["abc","ab"]
• Adding duplicate edges and over-counting in-degree, breaking the topological sort
• Initialising in-degree only for source characters and missing destination-only nodes
• Missing the cycle-detection step at the end — output length must equal node count
• Comparing all positions in a pair instead of breaking on the first difference

Interview Tips#

• State the model out loud — directed graph with characters as nodes and edges from adjacent word comparison
• Walk through a small example before coding to validate the edge derivation
• Use Kahn BFS over DFS — easier to argue and easier to implement under pressure
• Discuss why DFS with three-color marking also works as a backup approach
• Call out the two failure modes — cycle and prefix violation — by name

Follow-up Questions#

• What if the alphabet is Unicode, not just lowercase English? (Hint: still O(C), use a hashmap not a 26-array)
• Return all valid topological orders. (Hint: backtracking with in-degree maintenance)
• Verify whether a given order is consistent with the dictionary. (Hint: precompute index map then sweep)
• Solve LeetCode 207 Course Schedule using the same technique. (Hint: topological sort on prerequisites)
• Detect the smallest set of removed pairs to make the dictionary consistent. (Hint: minimum feedback arc set, NP-hard in general)

Key Takeaways#

• LeetCode 269 is the canonical Google topological sort problem
• Adjacent word comparisons yield exactly one edge per pair
• Kahn BFS produces an order in O(C) and detects cycles by length mismatch
• The prefix-invalid case is the trickiest edge — handle it before building the graph
• The graph has at most 26 nodes for English lowercase, so the constants are tiny
• Multiple valid orders may exist — any one is acceptable
• The same pattern solves Course Schedule, Build Order, and Task Dependency problems