Katkat
Back

Infer an Unknown Alphabet Order

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's competency in graph-based reasoning, inference of ordering constraints from sequences of strings, and algorithmic manipulation of characters and relations.

You are given a list of words that is already sorted according to an unknown alphabet. Derive one valid ordering of the characters in that alphabet.

Rules:

  • Each word consists of lowercase letters.
  • If multiple valid character orders exist, return any of them.
  • If the input is invalid because a longer word appears before its exact prefix, return an empty string.
  • If the ordering constraints contain a cycle, return an empty string.

Example:

  • Input: ["wrt", "wrf", "er", "ett", "rftt"]
  • One valid output: "wertf"

Follow-up: explain the exact time and space complexity in terms of the number of words, the total number of characters across all words, and the number of distinct letters.