Recover an Alien Alphabet from Sorted Words
Updated
Problem statement
A page torn from an alien dictionary has been recovered. The language writes with the letters a to z, yet its alphabet arranges them in a secret order of its own. The words on the page, given as words, are believed to follow the dictionary order of that alphabet.
Recover the secret order. Your answer is a string made of exactly the letters that occur in words, each used once, arranged from earliest to latest in the alien order.
An answer is valid when every word and the word right after it in the list obey these rules, with letters compared by their position in your answer:
- If the two words have different letters at some position, look at the leftmost such position. There, the letter of the first word must be earlier in the alien order than the letter of the second word. Letters after that position do not matter.
- If the two words agree at every position they both have, the first word must not be the longer one. So a word may be followed by itself or by a longer word that starts with it, but never by a shorter word it begins with.
When several answers are valid, the expected one is whichever sorts first when answers are compared letter by letter in the normal alphabet. If there is no valid answer, return "".
Function
alienOrder(words: String[]) → StringExamples
Example 1
words = ["ba","bc","ac","cab"]return = "bac"Only the first mismatch in each neighboring pair matters. In "ba" / "bc" it is a against c, so a is earlier. In "bc" / "ac" it is b against a, so b is earlier. In "ac" / "cab" it is a against c once more. Exactly one order fits: b, then a, then c.
Example 2
words = ["zx","zy","w"]return = "xyzw"The pair "zx" / "zy" puts x ahead of y, and the pair "zy" / "w" puts z ahead of w. Six orders satisfy both, for example "zwxy" and "xyzw". Of those six, "xyzw" sorts first as an ordinary string.
Example 3
words = ["pqr","pq"]return = ""The two words agree on p and q, and then "pqr" still has an r while "pq" has ended. The rules forbid a longer word right before its own beginning whatever the letter order is, which leaves no valid answer: return "".
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100- Only the letters
atozappear in the input.
More OpenAI Phone Screen questions
- Secret Number Search with One-Call-Delayed FeedbackPHONE SCREEN · Seen Nov 2026
- Determine the Winner of Three-Card HandsPHONE SCREEN · Seen Nov 2026
- Grid Infection with Recovery After D DaysPHONE SCREEN · Seen Nov 2026
- Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Light Source Hits: Sample, Compare, and FitPHONE SCREEN · Seen Nov 2026
- Rectangle Point Coverage CountsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Adaptive Calibration ErrorPHONE SCREEN · Seen Nov 2026
- Elevator Scheduling SimulationPHONE SCREEN · Seen Nov 2026
- Evaluate Noisy AnnotatorsPHONE SCREEN · Seen Oct 2026
- Network Endpoint or Cycle BoundaryOA · PHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Alien DictionaryByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Infer a Lexicographically Smallest Alien AlphabetMicrosoft · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- Alien Dictionary OrderGoogle · PHONE SCREENGoogle interview questions
- Letter Order from a Sorted Word ListRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Evaluate Formulas with Cycle DetectionInstacart · PHONE SCREEN · ONSITE INTERVIEWInstacart interview questions
- Validate CSV References and Field DependenciesStripe · PHONE SCREENStripe interview questions
- Alien DictionaryIntuit · OAIntuit interview questions
- Alien DictionaryBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Alien DictionaryAmazon · ONSITE INTERVIEW
- Password From Ordering HintsRogo · ONSITE INTERVIEW