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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

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

Determine order of alien alphabet | Citadel Coding Question

Quick Overview

This question evaluates the ability to infer ordering constraints among characters, model dependencies from ordered examples, and reason about edge cases in lexicographic sequences. Commonly asked in Coding & Algorithms interviews, it assesses both practical algorithmic implementation and conceptual understanding within the domains of string processing and graph-based ordering problems.

Determine order of alien alphabet

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a list of words sorted in lexicographic order according to an unknown ("alien") alphabet. ### Task Return **one valid ordering of the unique characters** in this alien alphabet that is consistent with the given sorted word list. If **no valid ordering exists**, return an empty string. ### Details - The alien alphabet contains exactly the set of distinct characters that appear in the input words. - The input list `words` is already sorted according to the alien alphabet. - If multiple valid character orders exist, you may return any one of them. ### Input - `words`: an array of strings, length `n`. ### Output - A string containing all distinct characters exactly once in a valid order, or `""` if impossible. ### Constraints (typical interview bounds) - `1 <= n <= 10^4` - `1 <= len(words[i]) <= 100` - Characters are lowercase English letters (you can assume an upper bound of 26 unique characters). ### Notes / Edge cases - If `word1` is a strict prefix of `word2`, then `word1` must appear before `word2` in the sorted list (otherwise the ordering is invalid). ### Example Input: `words = ["wrt", "wrf", "er", "ett", "rftt"]` Possible output: `"wertf"`

Quick Answer: This question evaluates the ability to infer ordering constraints among characters, model dependencies from ordered examples, and reason about edge cases in lexicographic sequences. Commonly asked in Coding & Algorithms interviews, it assesses both practical algorithmic implementation and conceptual understanding within the domains of string processing and graph-based ordering problems.

You are given a list of words sorted in lexicographic order according to an unknown alien alphabet. Return a valid ordering of all distinct characters that is consistent with the sorted list. If no such ordering exists, return an empty string. A character order can be inferred by comparing adjacent words and finding the first position where they differ. If one word is a strict prefix of another, then the shorter word must come first; otherwise the input is invalid. If multiple valid orders exist, any one would be logically correct. The reference solution returns a deterministic valid order.

Constraints

1 <= len(words) <= 10^4
1 <= len(words[i]) <= 100
Each word contains only lowercase English letters
There are at most 26 distinct characters across all words

Examples

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

Expected Output: "wertf"

Explanation: From adjacent comparisons we get w -> e, e -> r, r -> t, and t -> f, so a valid order is "wertf".

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

Expected Output: "zx"

Explanation: Comparing "z" and "x" gives z -> x, so the only valid order is "zx".

Input: (["ba", "bc", "ac", "cab"],)

Expected Output: "bac"

Explanation: The comparisons imply a -> c and b -> a, so the full valid order is b -> a -> c.

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

Expected Output: ""

Explanation: "abc" appears before its strict prefix "ab", which is impossible in a valid lexicographic ordering.

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

Expected Output: ""

Explanation: The list implies z -> x and x -> z, creating a cycle, so no valid alphabet exists.

Input: (["aaa"],)

Expected Output: "a"

Explanation: There is only one distinct character, so the answer is simply "a".

Hints

Only the first differing character between two adjacent words tells you anything about the order.
Build a directed graph of character precedence rules, then use topological sorting. Don't forget to check the invalid prefix case.

Last updated: Jun 9, 2026

Loading coding console...

Quick Overview

Determine order of alien alphabet

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Constraints

1 <= len(words) <= 10^4
1 <= len(words[i]) <= 100
Each word contains only lowercase English letters
There are at most 26 distinct characters across all words

Examples

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

Expected Output: "wertf"

Explanation: From adjacent comparisons we get w -> e, e -> r, r -> t, and t -> f, so a valid order is "wertf".

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

Expected Output: "zx"

Explanation: Comparing "z" and "x" gives z -> x, so the only valid order is "zx".

Input: (["ba", "bc", "ac", "cab"],)

Expected Output: "bac"

Explanation: The comparisons imply a -> c and b -> a, so the full valid order is b -> a -> c.

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

Expected Output: ""

Explanation: "abc" appears before its strict prefix "ab", which is impossible in a valid lexicographic ordering.

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

Expected Output: ""

Explanation: The list implies z -> x and x -> z, creating a cycle, so no valid alphabet exists.

Input: (["aaa"],)

Expected Output: "a"

Explanation: There is only one distinct character, so the answer is simply "a".

Hints

Only the first differing character between two adjacent words tells you anything about the order.
Build a directed graph of character precedence rules, then use topological sorting. Don't forget to check the invalid prefix case.

Last updated: Jun 9, 2026

Loading coding console...