Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Uber SWE interview with a graph/topology problem that looked like a word puzzle but was really a cycle detection question in disguise. Not a bad experience, just needed to recognize what kind of problem it actually was faster.

Questions Asked (1)

You're given a list of words sorted in lexicographic order according to an unknown alien alphabet. Reconstruct a valid ordering of the letters, or return an empty string if no valid ordering exists.

Algorithms & Data Structures

Author's notes

Took me a minute to see past the alien language flavor text and realize this is just topological sort.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a directed graph where each letter is a node and edges represent the relative order derived from adjacent words. Perform a topological sort to find a valid ordering, detecting cycles to return an empty string if none exists. Handle edge cases like invalid prefixes and duplicate words.

Pro tip: When comparing adjacent words, only the first differing character gives a valid ordering constraint; also, if a shorter word appears after a longer word with the shorter as a prefix, the ordering is invalid. Explicitly check these cases to avoid incorrect results.

1. Build the graph

Initialize a set of all unique characters and an adjacency list. 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.

2. Validate prefix condition

While comparing adjacent words, if the first word is longer and the second word is a prefix of the first, return an empty string immediately because the ordering is invalid.

3. Topological sort

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

4. Construct and return result

If the topological sort completes without cycles, concatenate the nodes in the order they are visited to form the alien alphabet string. Return this string.

Key Points to Mention

Graph representation: nodes are letters, edges represent order constraints from adjacent word comparisons.
Topological sorting algorithms: Kahn's algorithm (BFS) or DFS with cycle detection.
Cycle detection: if the graph has a cycle, no valid ordering exists, so return empty string.
Edge case: a word cannot be a prefix of a previous word in a valid lexicographic order.
Time complexity: O(N * L + V + E) where N is number of words, L is max word length, V is number of unique letters, E is number of edges.
Space complexity: O(V + E) for storing the graph and auxiliary data structures.

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