Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE interview with a string/sorting problem that sounds simple on the surface but has a few gotchas once you start coding it up.

Questions Asked (1)

Given a list of words written in an alien language that uses lowercase English letters but in a custom alphabet order, determine whether the words are sorted lexicographically according to that alien ordering.

Algorithms & Data Structures

Author's notes

The setup sounds weird but it's basically just a custom comparator problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, derive the alien alphabet order by comparing adjacent words and extracting character precedence constraints. Then, build a directed graph from these constraints and perform a topological sort to check for cycles, which would indicate an invalid ordering. Finally, verify that each adjacent pair of words is sorted according to the derived order.

Pro tip: Pay special attention to edge cases like duplicate words, empty strings, and words where one is a prefix of the other—these often trip up candidates. Also, clarify with the interviewer whether the alien alphabet is guaranteed to contain all 26 letters or just a subset.

1. Clarify assumptions and edge cases

Ask the interviewer about the alphabet size, whether all letters are used, and how to handle duplicate words or prefix relationships. This ensures you cover all constraints before coding.

2. Extract ordering constraints

Iterate through adjacent word pairs and find the first differing character to establish a precedence rule (e.g., 'a' comes before 'b'). If no differing character is found, ensure the shorter word is not longer than the next word (prefix rule).

3. Build and validate the graph

Construct a directed graph where an edge from u to v means u precedes v in the alien alphabet. Check for cycles using topological sort (Kahn's algorithm or DFS); a cycle means the ordering is invalid.

4. Verify sorted order

Using the derived alphabet order, compare each adjacent pair of words lexicographically to confirm they are sorted. If any pair is out of order, return false.

5. Analyze complexity and optimize

Discuss time and space complexity: O(N * L + V + E) where N is number of words, L is max word length, V is alphabet size, and E is number of precedence edges. Mention potential optimizations like early termination.

Key Points to Mention

Topological sorting to detect cycles and derive a valid alphabet order.
Handling prefix cases: if one word is a prefix of another, the shorter must come first.
Graph representation: adjacency list and indegree array for efficient cycle detection.
Time and space complexity analysis, including worst-case scenarios.
Edge cases: duplicate words, empty strings, and words with no differing characters.
Clarifying assumptions about the alien alphabet (e.g., whether it includes all 26 letters).

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