Katkat
Back

Reason About Alien Dictionary Ordering

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests the ability to model lexicographical constraints as a directed graph and determine if a valid ordering of unique characters exists using topological sorting.

Alien Dictionary Ordering

In an alien language, the alphabet is a variation of the English alphabet, but the order of the letters is unknown to you. You are given a list of non-empty words from the dictionary, sorted lexicographically by the rules of this alien language.

Your task is to determine if the given sequence of words is consistent with any valid alien dictionary character ordering. If it is consistent, return a string of all unique characters in the alien alphabet sorted in valid order. If there are multiple valid orders, return any one of them. If the sequence is invalid, return an empty string.

Function Signature

def alienOrder(words: List[str]) -> str:

Constraints

  • 1 <= words.length <= 100
  • 1 'e', 'r' -> 't', 'f' -> 't' implies the order w, e, r, t, f`.

Example 2: Input: words = ["z","x","z"] Output: "" Explanation: The order is invalid because 'z' cannot come before 'x' and 'x' cannot come before 'z' (cycle).

Edge Cases

  • Prefix cases: If word A is a prefix of word B, A must come before B. If B is a prefix of A, the order is invalid (e.g., ["abc", "ab"] is impossible).
  • Disconnected components: Some characters may not have specified relationships; ensure all unique characters are included in the result.

Hints

Hint 1

Model the characters as nodes in a graph and draw directed edges based on the first differing character between adjacent words in the list.

Hint 2

Perform a topological sort using Kahn's algorithm (indegree counting) or DFS to detect cycles and determine the linear order.

Hint 3

Explicitly check for the prefix constraint: if a longer word appears before a shorter word that is its prefix, return an empty string immediately.

Follow-up questions

  • How would your algorithm change if you needed to return the lexicographically smallest possible ordering among all valid orders?
  • What is the time and space complexity of your solution in terms of total characters and the size of the alphabet?
  • If the input list is very large, how could you optimize the graph construction process to avoid redundant edge additions?