How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Infer an Unknown Alphabet Order | Meta Coding Question

Infer an Unknown Alphabet Order

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: 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. Reconstruct one valid ordering of all distinct characters that appear in the words. Rules: - Each word contains only lowercase letters. - If a longer word appears before its exact prefix, the input is invalid and you must return an empty string. - If the implied ordering constraints contain a cycle, return an empty string. - Characters that appear in the input but are not constrained relative to others must still appear in the result. For deterministic test outputs in this version of the problem, if multiple valid orders exist, return the lexicographically smallest valid order. Follow-up: explain the time and space complexity in terms of W = number of words, C = total number of characters across all words, and K = number of distinct letters.

Constraints

0 <= len(words) <= 10^4
1 <= len(word) <= 100 for each word when words is non-empty
The total number of characters across all words is at most 10^5
Each word contains only lowercase English letters, so the number of distinct letters K is at most 26

Examples

Input: (["wrt", "wrf", "er", "ett", "rftt"],)

Expected Output: "wertf"

Explanation: The constraints are t -> f, w -> e, r -> t, and e -> r, which produce the order wertf.

Input: (["abc", "ab"],)

Expected Output: ""

Explanation: A longer word appears before its exact prefix, so the input is invalid.

Input: (["z", "x", "z"],)

Expected Output: ""

Explanation: From z before x we get z -> x, and from x before z we get x -> z, which forms a cycle.

Input: ([],)

Expected Output: ""

Explanation: There are no words and therefore no characters to order.

Input: (["abc", "abc"],)

Expected Output: "abc"

Explanation: There are no ordering constraints between characters, so the lexicographically smallest valid order is abc.

Input: (["za", "zb", "ca", "cb"],)

Expected Output: "abzc"

Explanation: The constraints are a -> b and z -> c. The lexicographically smallest topological order is abzc.

Input: (["z", "x"],)

Expected Output: "zx"

Explanation: The first differing characters imply z -> x, so the order must be zx.

Hints

Compare only adjacent words. The first position where they differ gives you one directed ordering constraint.
After building a graph of character dependencies, use topological sorting. Tracking indegrees helps detect cycles, and a min-heap gives the lexicographically smallest valid order.

Quick Overview

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.