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.