Uber·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Uber ML engineer interview with a classic alphabet ordering problem. Pretty standard algorithmic round, nothing too wild, but the question has a few edge cases that can trip you up if you're not careful.

Questions Asked (1)

You're given a list of strings that are sorted lexicographically in some unknown language. Figure out the correct ordering of the letters in that language's alphabet.

Algorithms & Data Structures

Author's notes

Classic topological sort problem dressed up in a fun disguise.

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. Then perform a topological sort to find a valid alphabet order, detecting cycles if the input is invalid.

Pro tip: Always check for invalid cases like cycles or prefix violations (e.g., 'abc' before 'ab') and mention them explicitly—this shows attention to edge cases and robustness, which is crucial for production ML systems.

1. Extract ordering constraints

Iterate through adjacent pairs of words and find the first differing character to establish a directed edge from the earlier word's character to the later word's character.

2. Build the graph

Create a graph with all unique characters as nodes and add directed edges for each constraint. Also track in-degrees for topological sorting.

3. Topological sort

Use Kahn's algorithm (BFS with in-degree tracking) or DFS to produce a linear ordering of the letters. If a cycle is detected, the input is invalid.

4. Handle edge cases

Check for prefix violations (e.g., 'abc' before 'ab') which make the order invalid. Also ensure all letters are included, even those not appearing in constraints.

5. Return the order

If the topological sort succeeds, return the resulting order of letters as the alphabet. Otherwise, indicate that no valid order exists.

Key Points to Mention

Graph representation: nodes are letters, edges represent relative order.
Topological sorting algorithms: Kahn's (BFS) or DFS with cycle detection.
Cycle detection: if a cycle exists, the input is inconsistent.
Prefix violation: a longer word cannot come before its prefix.
Time complexity: O(N + E) where N is number of letters and E is number of edges.
Space complexity: O(N + E) for graph and in-degree storage.

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