Check and infer custom alphabet
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are working with an unknown language that uses a custom alphabetical order, such as `['a', 'd', 'c', 'b', ...]`.
Implement the following:
1. **Check sorted order**: Given a custom alphabet order and an array of strings, determine whether the strings are sorted in nondecreasing lexicographic order under that alphabet.
2. **Follow-up**: Given an array of strings that is already sorted according to an unknown custom alphabet, infer **one possible** alphabet order that is consistent with the given list. If no valid order exists, return that it is impossible.
Assumptions:
- All strings consist of lowercase letters.
- Lexicographic comparison is based on the first differing character.
- If one word is a prefix of another, the shorter word must come first.
- In the follow-up, if multiple valid alphabet orders exist, returning any one of them is acceptable.
Quick Answer: This question evaluates understanding of string comparison under a custom lexicographic order, the ability to validate whether a list of words is sorted according to that order, and the ability to infer a consistent character precedence from an ordered list.