Verify Ordering Under a Scrambled Alphabet
Company: Truefoundry
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Verify Ordering Under a Scrambled Alphabet
Given a sequence of words and an alphabet string that lists every allowed character from smallest to largest, determine whether the words are sorted in nondecreasing lexicographic order under that alphabet. If one word is a prefix of another, the shorter word comes first.
## Function Contract
Implement `is_alien_sorted(words, alphabet) -> bool`.
## Constraints
- 0 <= number of words <= 100000.
- The total number of characters across all words is at most 500000.
- The alphabet and every word contain only printable ASCII characters with code values from 32 through 126.
- The alphabet contains unique characters, and every word character appears in it.
- Equal adjacent words are allowed.
## Examples
```text
words = ["cat", "bat", "tab"], alphabet = "cbat"
output = true
```
```text
words = ["apple", "app"], alphabet = "abcdefghijklmnopqrstuvwxyz"
output = false
```
```hint Exercise boundary words
Include equal adjacent words, an empty word, and pairs where one word is a prefix of the other.
```
```hint Respect the supplied alphabet
Do not assume ordinary English order or apply case folding that the input alphabet does not define.
```
Quick Answer: Given a sequence of words and an alphabet string that lists every allowed character from smallest to largest, determine whether the words are sorted in nondecreasing lexicographic order under that alphabet. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given `words` and an `alphabet` listing every allowed printable ASCII character from smallest to largest, return whether the words are in nondecreasing lexicographic order under those ranks. Equal adjacent words are allowed. When one word is a prefix of another, the shorter word comes first. Character comparison is case-sensitive.
Constraints
- 0 <= len(words) <= 100000, with at most 500000 total word characters.
- alphabet and every word use printable ASCII characters with codes 32 through 126.
- alphabet contains unique characters and includes every character used by the words.
- Equal adjacent words are valid; an exact prefix must appear before the longer word.
Examples
Input: ([], ' !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~')
Expected Output: True
Explanation: An empty sequence is sorted.
Input: ([''], ' !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~')
Expected Output: True
Explanation: A singleton empty word is sorted.
Hints
- Test equal adjacent words, an empty word, and both orders of a prefix pair.
- Use a case-sensitive custom alphabet whose order differs from ordinary ASCII.
- Include spaces, punctuation, and a pair whose first difference occurs late in the words.