Alien Dictionary Variant | Dataford Interview Questions

How would you solve a variant of the alien dictionary problem, and what edge cases would you watch for?

Implement the function below. Return the lexicographically smallest valid character ordering, or "" if the sorted words imply a cycle or an invalid prefix. Include every distinct character, including characters with no ordering constraints.

Input/output contract: words is a list of lowercase strings. The function returns a string containing each distinct character exactly once, or "" when no valid ordering exists.

Constraints

1 <= words.length <= 10^4
1 <= words[i].length <= 100
Each word contains only lowercase English letters
The total number of characters across all words is at most 10^5
Return the lexicographically smallest valid ordering when multiple orderings exist

Function Signature

def alien_order(words):

Your question is Alien Dictionary Variant. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

How would you solve a variant of the alien dictionary problem, and what edge cases would you watch for?

Input/output contract: words is a list of lowercase strings. The function returns a string containing each distinct character exactly once, or "" when no valid ordering exists.

Constraints

1 <= words.length <= 10^4
1 <= words[i].length <= 100
Each word contains only lowercase English letters
The total number of characters across all words is at most 10^5
Return the lexicographically smallest valid ordering when multiple orderings exist

Function Signature

def alien_order(words):

Your question is Alien Dictionary Variant. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.