Infer an Unknown Alphabet Order
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of words that is already sorted according to an unknown alphabet. Derive one valid ordering of the characters in that alphabet.
Rules:
- Each word consists of lowercase letters.
- If multiple valid character orders exist, return any of them.
- If the input is invalid because a longer word appears before its exact prefix, return an empty string.
- If the ordering constraints contain a cycle, return an empty string.
Example:
- Input: `["wrt", "wrf", "er", "ett", "rftt"]`
- One valid output: `"wertf"`
Follow-up: explain the exact time and space complexity in terms of the number of words, the total number of characters across all words, and the number of distinct letters.
Quick Answer: This question evaluates a candidate's competency in graph-based reasoning, inference of ordering constraints from sequences of strings, and algorithmic manipulation of characters and relations.
You are given a list of words that is already sorted according to an unknown alphabet. Reconstruct one valid ordering of all distinct characters that appear in the words.
Rules:
- Each word contains only lowercase letters.
- If a longer word appears before its exact prefix, the input is invalid and you must return an empty string.
- If the implied ordering constraints contain a cycle, return an empty string.
- Characters that appear in the input but are not constrained relative to others must still appear in the result.
For deterministic test outputs in this version of the problem, if multiple valid orders exist, return the lexicographically smallest valid order.
Follow-up: explain the time and space complexity in terms of W = number of words, C = total number of characters across all words, and K = number of distinct letters.
Constraints
- 0 <= len(words) <= 10^4
- 1 <= len(word) <= 100 for each word when words is non-empty
- The total number of characters across all words is at most 10^5
- Each word contains only lowercase English letters, so the number of distinct letters K is at most 26
Examples
Input: (["wrt", "wrf", "er", "ett", "rftt"],)
Expected Output: "wertf"
Explanation: The constraints are t -> f, w -> e, r -> t, and e -> r, which produce the order wertf.
Input: (["abc", "ab"],)
Expected Output: ""
Explanation: A longer word appears before its exact prefix, so the input is invalid.