Meta·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Meta SWE interview with a graph/topological sort problem that looks clean on the surface but has a few edge cases that'll trip you up if you're not careful.

Questions Asked (1)

Given a list of words sorted according to an unknown alien language's alphabet, determine a valid character ordering consistent with the sort. Return an empty string if no valid ordering exists (e.g. a cycle is detected, or a word appears before one of its own prefixes).

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The core idea clicked pretty fast: compare adjacent words, find the first character that differs, that gives you a directed edge.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Build a directed graph where each character is a node and edges represent the relative order derived from adjacent word pairs. Then perform a topological sort to find a valid character ordering, returning an empty string if a cycle is detected or if a word is a prefix of a previous word.

Pro tip: Explicitly handle the prefix violation case (e.g., 'abc' before 'ab') as an immediate invalid input, and mention that the graph may be disconnected, so you must include all unique characters from the input.

1. Validate input and extract characters

Check for prefix violations by comparing each word with its predecessor; if a word is shorter and a prefix of the previous word, return empty string. Collect all unique characters from the list to ensure the graph includes every character.

2. Build the graph

For each pair of adjacent words, find the first differing character and add a directed edge from the character in the first word to the character in the second word. If no differing character is found, the words are identical or one is a prefix (already handled).

3. Topological sort

Perform a topological sort on the graph using either Kahn's algorithm (BFS with in-degree) or DFS with cycle detection. If a cycle is detected, return an empty string.

4. Construct and return the ordering

If the topological sort succeeds, concatenate the characters in the order produced to form the alien alphabet string. If multiple valid orderings exist, any is acceptable.

Key Points to Mention

Graph representation: adjacency list for characters, with edges derived from adjacent word comparisons.
Cycle detection: use Kahn's algorithm (if processed nodes < total nodes) or DFS with recursion stack to detect cycles.
Prefix violation: if a word is a prefix of the previous word, the input is invalid and should return empty string.
Time complexity: O(N * L) where N is number of words and L is max word length, plus O(V+E) for topological sort.
Space complexity: O(V+E) for graph storage, where V is unique characters (≤ 26) and E is number of edges.
Handling disconnected graphs: include all unique characters as nodes, even if they have no edges, to ensure a complete ordering.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.