Katkat
Back

Infer an Alien Alphabet from Sorted Words

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests graph theory knowledge, specifically topological sorting using Kahn's algorithm or DFS, applied to dependency resolution between characters.

Alien Language Ordering

You are given a list of words from an alien language, which is sorted lexicographically according to the rules of that alien alphabet. Write a function to determine the order of characters in this alphabet.

If the input is invalid (e.g., "abc" comes before "ab", which is impossible in dictionary order), return an empty string. If there are multiple valid orderings, return the one that is lexicographically smallest when comparing the character sequences themselves.

Function Signature

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

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • Words contain only lowercase English letters.

Examples

Example 1: Input: words = ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf" Explanation:

  • 'w' < 'e' (from "wrt" vs "er")
  • 'r' < 't' (from "wrt" vs "wrf")
  • 't' < 'f' (from "wrf" vs "er")
  • 'e' < 'r' (from "er" vs "ett")

Example 2: Input: words = ["z", "x", "z"] Output: "" Explanation: The order is invalid because "z" cannot be smaller than "x" and simultaneously "x" smaller than "z".

Edge Cases

  • Single word lists.
  • Prefix conflicts (e.g., ["abc", "ab"]).
  • Disconnected components in the graph (characters not appearing in the ordering constraints).

Hints

Hint 1

Represent the alien alphabet as a directed graph where an edge from character A to B means A comes before B.

Hint 2

Build the graph by comparing adjacent words to find the first differing character, which dictates the precedence.

Hint 3

Use Kahn's algorithm (BFS with in-degrees) to find the topological sort and ensure it handles disconnected components by including all unique characters found in the input.

Follow-up questions

  • How would you modify your solution to handle uppercase and lowercase letters as distinct characters?
  • What is the time and space complexity of your solution in terms of total characters and alphabet size?
  • If the input words contained a massive number of characters, how would you optimize the graph representation?