Infer the Smallest Valid Character Order from Sorted Password Hints
Company: Rogo
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Infer the Smallest Valid Character Order from Sorted Password Hints
You are given password hints already sorted according to an unknown alphabet. Infer a character order consistent with the list.
Implement infer_password_order(words). Include every distinct lowercase English letter that appears in words exactly once. If several valid orders exist, return the lexicographically smallest one under normal a-to-z order. Return the empty string when the hints are inconsistent because of a directed cycle or because a longer word appears immediately before its exact prefix.
## Input
- words: a list of lowercase strings sorted by the unknown alphabet.
## Output
- The canonical order string, or the empty string when no valid order exists.
## Constraints
- 0 <= words.length <= 10000
- 0 <= words[i].length <= 100
- The total number of characters is at most 200000.
```hint Compare adjacent hints
Only the first differing character in each adjacent pair creates an ordering edge. Use a min-priority topological traversal so that every choice among currently available characters is canonical.
```
Quick Answer: A graph and topological-sorting interview problem about inferring an alphabet from sorted password hints. Candidates must detect invalid prefixes and cycles, include every observed character, and return the lexicographically smallest valid order.
Implement infer_password_order(words). Include every distinct lowercase English letter that appears in the hints exactly once. Return the lexicographically smallest order consistent with the sorted hints, or the empty string when a directed cycle exists or a longer word immediately precedes its exact prefix.
Constraints
- 0 <= words.length <= 10000
- 0 <= words[i].length <= 100
- The total number of characters is at most 200000
- Every character is a lowercase English letter
Examples
Input: ([],)
Expected Output: ''
Explanation: No observed characters produce the empty order.
Input: ([''],)
Expected Output: ''
Explanation: An empty hint contributes no characters or constraints.
Hints
- Compare adjacent hints and use only their first differing characters.
- Reject a longer hint that appears immediately before its exact prefix.
- Use a min-priority queue during topological sorting to make every tie deterministic.