Uber·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026Remote

Summary

Phone screen for a SWE role at Uber. They threw LC 269 at me straight up, no warmup, and then followed it with the verify-only variant as a back-to-back. Not a bad round but it was denser than I expected for a phone screen.

Questions Asked (2)

Given a list of words sorted in an unknown alien lexicographic order, recover any valid character ordering. Return an empty string if no valid ordering exists.

Algorithms & Data Structures

Author's notes

This is the classic topological sort problem on 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 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 the input is invalid (e.g., a longer word precedes its prefix).

Pro tip: Always validate the input first: if a word is longer than the next word and the next word is its prefix, the ordering is impossible. Also, remember to include all unique characters from the words in the graph, even those with no edges, to produce a complete ordering.

1. Validate input and build character set

Check for invalid cases where a longer word appears before its prefix in the list. Collect all unique characters from all words to ensure the final ordering 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. Use a set to avoid duplicate edges.

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 sorted order. Ensure all characters from the character set are included; if not, append any remaining characters (they can be placed anywhere).

Key Points to Mention

Graph representation: nodes are characters, edges represent order constraints from adjacent word comparisons.
Cycle detection: a cycle indicates no valid ordering, so return empty string.
Invalid prefix case: if a word is longer than the next and the next is its prefix, return empty string.
Topological sort algorithms: Kahn's algorithm (BFS) or DFS with recursion stack.
Handling disconnected components: include all unique characters, even those with no edges.
Time and space complexity: O(N * L + V + E) where N is number of words, L is max word length, V is unique characters, E is edges.

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

Given a fixed 26-character permutation defining an alien alphabet, verify whether a list of words is already sorted under that ordering.

Algorithms & Data Structures

Author's notes

Came right after the first question with almost no break.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Map each character of the alien alphabet to its index (0-25) to create a rank lookup. Then iterate through the list of words, comparing each adjacent pair lexicographically using the rank lookup. If any pair is out of order, return false; otherwise return true.

Pro tip: Clarify edge cases upfront: empty word list, single word, and words where one is a prefix of the other (e.g., 'app' vs 'apple'). Also, mention that you can early-exit on the first out-of-order pair for efficiency.

1. Build the rank mapping

Create an array or hash map that maps each character in the alien alphabet to its position (0 to 25). This allows O(1) comparisons.

2. Iterate through adjacent word pairs

Loop from i = 0 to n-2, comparing words[i] and words[i+1] using the alien order. If any pair is out of order, return false immediately.

3. Compare two words lexicographically

For each pair, iterate character by character up to the minimum length. If characters differ, compare their ranks; if the first word's rank is greater, it's out of order. If all characters match, the shorter word must come first (or they are equal).

4. Handle prefix cases and return result

If one word is a prefix of the other, ensure the shorter word appears first. If all pairs are in order, return true.

Key Points to Mention

Time complexity: O(N * L) where N is number of words and L is average word length, since each character is compared at most once per adjacent pair.
Space complexity: O(1) for the rank mapping (fixed 26 characters) plus O(1) extra for comparisons.
Edge cases: empty list, single word, duplicate words, and words where one is a prefix of another.
Early termination: return false as soon as an out-of-order pair is found.
Use of a hash map or array for O(1) rank lookups.
Lexicographic comparison logic: compare character by character, and if one word is a prefix, the shorter word must come first.

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