Given a list of words sorted lexicographically by the rules of an unknown alien language, derive the order of characters in that language.
For example:
Input: ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf"
Explanation: - Comparing "wrt" and "wrf": 't' comes before 'f' - Comparing "wrf" and "er": 'w' comes before 'e' - Comparing "er" and "ett": 'r' comes before 't' - Comparing "ett" and "rftt": 'e' comes before 'r'
So the order is: w -> e -> r -> t -> f
How do you extract ordering information from adjacent words? What graph algorithm applies here? When is the answer invalid or ambiguous?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
Compare each pair of adjacent words to find the first differing character. That gives you an ordering constraint: the character in the first word comes before the character in the second word.
- Hint 2
Build a directed graph from these constraints and perform a topological sort to find the character order.
- Hint 3
Watch for invalid inputs: if a longer word appears before its prefix (e.g., 'abc' before 'ab'), the ordering is invalid. If the graph has a cycle, no valid ordering exists.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.