Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Meta SWE coding round, one question the whole time: alien dictionary. Felt manageable going in but the corner cases have a way of humbling you mid-implementation.

Questions Asked (1)

Given a list of words sorted in an unknown alphabet's lexicographic order, return a valid ordering of the letters in that alphabet. Return an empty string if no valid ordering exists.

Algorithms & Data Structures

Author's notes

I knew the general shape of the solution: build a directed graph from adjacent word pairs, run topological sort.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Build a directed graph of character precedence by comparing adjacent words to extract ordering constraints, then perform a topological sort to find a valid alphabet order. If a cycle is detected or the constraints are inconsistent (e.g., a longer word precedes its prefix), return an empty string.

Pro tip: Explicitly handle edge cases like duplicate words, a word being a prefix of the next, and cycles—interviewers at Meta often test these to see if you consider invalid inputs. Also, clarify that the alphabet may contain letters not present in the words, but the output should only include letters that appear.

1. Extract precedence constraints

Iterate through adjacent word pairs and find the first differing character to establish a directed edge from the earlier character to the later one. If the first word is longer and is a prefix of the second, the ordering is invalid, so return an empty string.

2. Build the graph

Represent each unique character as a node and add directed edges for each precedence constraint. Track in-degrees for all nodes to prepare for topological sorting.

3. Topological sort

Use Kahn's algorithm (BFS with a queue) or DFS to produce a linear ordering of characters. Start with nodes that have zero in-degree and repeatedly remove them, adding to the result.

4. Detect cycles

If the topological sort does not include all nodes (i.e., some nodes remain with non-zero in-degree), a cycle exists, meaning no valid ordering. Return an empty string in this case.

5. Return the result

If all nodes are processed, return the characters in the order produced by the topological sort as a string. Otherwise, return an empty string.

Key Points to Mention

Graph representation: adjacency list and in-degree array for efficient topological sorting.
Handling invalid cases: cycles and prefix violations (e.g., 'abc' before 'ab').
Time and space complexity: O(N * L) where N is number of words and L is max word length, plus O(V+E) for topological sort.
Choice of topological sort algorithm: Kahn's algorithm (BFS) vs. DFS, and why one might be preferred.
Edge cases: empty input, single word, duplicate words, and characters not appearing in any word.
Clarifying assumptions: the alphabet is a permutation of unique characters appearing in the words, and the given list is sorted according to that unknown alphabet.

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