Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Meta phone screen for a software engineer role, basically one algorithmic problem the whole time. The question was a graph/topology problem dressed up as a dictionary puzzle, which took me a minute to even recognize.

Questions Asked (1)

Given a list of words sorted by an unknown alphabet, derive a valid character ordering for that alphabet. Return an empty string if the input is invalid (a word appears before its own prefix) or if the constraints produce a cycle.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Took me longer than I'd like to admit to see this was just topological sort on a DAG of character constraints.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a directed graph where each character is a node and edges represent ordering constraints derived from adjacent word pairs. Then perform a topological sort to find a valid character order, detecting cycles and invalid prefix cases along the way.

Pro tip: Clarify edge cases upfront: if a word is a prefix of the previous word, return empty string immediately. Also, mention that multiple valid orders may exist, so any topological order is acceptable.

1. Validate input and handle edge cases

Check if any word is a prefix of the previous word; if so, return empty string. Also handle empty input or single word by returning any order of unique characters.

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. Track all unique characters as nodes.

3. Topological sort

Perform a topological sort on the graph (e.g., using Kahn's algorithm or DFS). If a cycle is detected, return an empty string.

4. Return the result

If topological sort succeeds, return the characters in sorted order as a string. Otherwise, return empty string.

Key Points to Mention

Graph representation: adjacency list and in-degree array for Kahn's algorithm.
Cycle detection: if the topological sort does not include all nodes, a cycle exists.
Prefix validation: a word appearing before its own prefix makes the input invalid.
Time and space complexity: O(C) where C is total characters, or O(N + E) with N nodes and E edges.
Handling multiple valid orders: any valid topological order is acceptable.
Edge cases: empty list, single word, duplicate words, and characters not appearing in any edge.

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