Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Microsoft coding round, graph-based problem that looks straightforward until you actually try to implement it cleanly under pressure. Topological sort with a side of edge cases nobody warns you about.

Questions Asked (1)

Given a sorted word list from an alien language, figure out the character ordering that's consistent with that dictionary. Build a directed graph by comparing adjacent words and return a valid topological order, or an empty string if a cycle exists or a word appears before its own prefix.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I got the core idea pretty fast, compare adjacent words character by character, first difference gives you a directed edge.

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 comparing adjacent words. Then perform a topological sort (e.g., Kahn's algorithm) to find a valid character order, detecting cycles or invalid prefix cases that would make the order impossible.

Pro tip: Explicitly handle the prefix edge case: if a shorter word appears after a longer word that is its prefix, the dictionary is invalid. Also, mention that multiple valid orders may exist, so any topological order is acceptable.

1. Build the graph

Iterate through adjacent word pairs, compare characters until a difference is found, and add a directed edge from the first differing character to the second. If no difference is found and the first word is longer, return an empty string immediately.

2. Compute in-degrees

Initialize an in-degree count for each character that appears in the word list. For each edge added, increment the in-degree of the destination character.

3. Topological sort

Use a queue to process all characters with in-degree 0, appending them to the result. For each processed character, decrement the in-degree of its neighbors and enqueue any that reach 0.

4. Detect cycles

After processing, if the result length is less than the total number of unique characters, a cycle exists. Return an empty string in that case.

5. Return result

If no cycle is detected, return the topological order as a string. This order is a valid character ordering consistent with the alien dictionary.

Key Points to Mention

Graph construction from adjacent word comparisons
Topological sorting using Kahn's algorithm (BFS) or DFS
Cycle detection via in-degree counts or visited states
Prefix edge case: shorter word before longer word that is its prefix
Time and space complexity: O(C) where C is total characters in all words
Handling of multiple valid orders and returning any one

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