Coding · Graphs and grids
Alien Dictionary
- Reported in several places
- Hard
- SDE II
- 3 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
A list of words is sorted according to the dictionary order of an unknown alphabet. Work out an ordering of the letters that is consistent with the list, or return an empty string if no ordering can exist. For ["wrt","wrf","er","ett","rftt"] the answer is "wertf". Words use lowercase letters, every distinct letter must appear in the answer, and when several orders are valid return the one that is smallest as a string.
Restated in our own words, not a quote from Uber or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
First I would check whether the list is guaranteed to come from a real alphabet or may contradict itself, and what to return if it does. What if a word is a prefix of the next one, or a longer word comes before its own prefix? Must letters that are never compared still appear in the answer? Can the list be empty or hold a single word? How large can it be?
I would assume lowercase letters, that every distinct letter must appear in the output, that a longer word placed before its own prefix is invalid, and that ties between equally valid letters are broken by picking the alphabetically smaller one, so the answer is unique.
Brute force
Say the obvious answer and why it is too slow.
Try every permutation of the distinct letters and test each one against the list. With 26 letters there are 26! permutations, about 4 × 10^26, so this stops being possible at around ten letters. Testing one candidate means checking each neighbouring pair of words, which costs a pass over all C characters.
A slightly smarter version compares every pair of words, which is O(n² · L) work for n words of length at most L, but it collects nothing that neighbouring words do not already give you. The real problem is that guessing the order wastes everything the list tells you. We should build the order from the constraints instead of searching for it.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(V! · C)
- Time
- O(C + V² log V)
- Space
- O(V + E)
The pattern is a topological sort on letters. Each pair of neighbouring words gives at most one fact. Scan both words until the first position where they differ: the letter in the first word must come before the letter in the second word. That is one directed edge. Later positions say nothing. If there is no differing position, the shorter word must come first; if the longer one comes first, the input is contradictory and the answer is empty.
Now any valid alphabet is exactly an ordering of the letters in which every edge points forward, which is a topological order of this graph. Kahn's algorithm builds one. Count each letter's incoming edges, output a letter with none, delete its outgoing edges, and release any letter whose count drops to zero. If the output holds every letter we are done. Letters that never reach zero are on a cycle, such as a before b and b before a, or sit behind one, so no order exists and we return an empty string.
Why only neighbouring pairs? Dictionary order is transitive, so other pairs add no new facts. The output is correct because a letter is released only after everything that must precede it has been written.
When several letters are free at once, any choice is valid, so to return one canonical answer I keep the free letters sorted and always take the smallest. With C total characters, V distinct letters and E edges, reading the words costs O(C), and the peeling touches each letter and edge once plus a sort of the free letters, at most 26 of them. Out loud: "build edges from the first difference, then peel off letters with no unmet prerequisites."
Walk it through
A dry run on the example, step by step.
| step | take | frees | ready next | output |
|---|---|---|---|---|
| 0 | start | - | w | (empty) |
| 1 | w | e | e | w |
| 2 | e | r | r | we |
| 3 | r | t | t | wer |
| 4 | t | f | f | wert |
| 5 | f | nothing | none | wertf |
Take ["wrt","wrf","er","ett","rftt"]. Neighbouring pairs give four edges. wrt and wrf first differ at the last letter, so t comes before f. wrf and er differ at the first letter, so w before e. er and ett differ at the second letter, so r before t. ett and rftt differ at the first letter, so e before r. Only w has no incoming edge.
The trace shows the peeling. Take w, which frees e. Take e, which frees r. Take r, which frees t. Take t, which frees f. Take f. All five letters are out, so the answer is "wertf". Exactly one letter was free at every step, so the sorted tie-break never had to choose.
The code
Runnable JavaScript, checked against test cases.
function alienOrder(words) {
const after = new Map();
const incoming = new Map();
for (const word of words) {
for (const letter of word) {
if (!after.has(letter)) {
after.set(letter, new Set());
incoming.set(letter, 0);
}
}
}
for (let i = 0; i + 1 < words.length; i++) {
const first = words[i];
const second = words[i + 1];
let k = 0;
while (k < first.length && k < second.length && first[k] === second[k]) k++;
if (k === Math.min(first.length, second.length)) {
if (first.length > second.length) return "";
continue;
}
if (!after.get(first[k]).has(second[k])) {
after.get(first[k]).add(second[k]);
incoming.set(second[k], incoming.get(second[k]) + 1);
}
}
const ready = [...incoming.keys()].filter((letter) => incoming.get(letter) === 0);
let order = "";
while (ready.length > 0) {
ready.sort();
const letter = ready.shift();
order += letter;
for (const next of after.get(letter)) {
incoming.set(next, incoming.get(next) - 1);
if (incoming.get(next) === 0) ready.push(next);
}
}
return order.length === incoming.size ? order : "";
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Empty list or one word: there are no edges, every letter is free, and the letters come out in sorted order. An empty list gives an empty string.
- Prefix trap: ["abc","ab"] is contradictory. The scan runs off the shorter word without finding a difference, and because the first word is longer the code returns an empty string. ["ab","abc"] is fine and adds no edge.
- Cycle: ["z","x","z"] gives z before x and x before z. Neither count reaches zero, the output is shorter than the letter count, and the function returns an empty string.
- Repeated facts: two pairs may give the same edge. The set of successors stops the incoming count being raised twice.
- Letters never compared: a letter that only appears after a shared prefix still gets a node and still appears in the output.
Follow-ups to expect
Where the interviewer pushes next.
- How would you find and report the actual cycle of letters instead of returning an empty string?
- How would you count the valid alphabets, or check that the order is unique?
- Can you solve it with a depth-first search, and what extra state do you need to detect a cycle?
- What changes if the symbols are arbitrary Unicode characters or whole tokens instead of lowercase letters?
Where candidates slip
The mistakes this problem punishes.
Common mistakes on this problem:
- Comparing only the first letters of neighbouring words instead of finding the first differing letter.
- Adding an edge for every differing position instead of only the first, which invents false constraints.
- Missing the prefix case, so ["abc","ab"] wrongly succeeds.
- Building nodes only from edges, which drops letters that have no edges.
- Counting a repeated edge twice, so a letter never reaches zero and a valid input is rejected.
- Returning a partial order when a cycle exists.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.