Quick Overview

This question evaluates understanding of string comparison under a custom lexicographic order, the ability to validate whether a list of words is sorted according to that order, and the ability to infer a consistent character precedence from an ordered list.

Check and infer custom alphabet

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are working with an unknown language that uses a custom alphabetical order, such as `['a', 'd', 'c', 'b', ...]`. Implement the following: 1. **Check sorted order**: Given a custom alphabet order and an array of strings, determine whether the strings are sorted in nondecreasing lexicographic order under that alphabet. 2. **Follow-up**: Given an array of strings that is already sorted according to an unknown custom alphabet, infer **one possible** alphabet order that is consistent with the given list. If no valid order exists, return that it is impossible. Assumptions: - All strings consist of lowercase letters. - Lexicographic comparison is based on the first differing character. - If one word is a prefix of another, the shorter word must come first. - In the follow-up, if multiple valid alphabet orders exist, returning any one of them is acceptable.

Quick Answer: This question evaluates understanding of string comparison under a custom lexicographic order, the ability to validate whether a list of words is sorted according to that order, and the ability to infer a consistent character precedence from an ordered list.

Check Sorted Order Under Custom Alphabet

Return whether words are nondecreasing under the supplied custom alphabet.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

Input: ('hlabcdefgijkmnopqrstuvwxyz', ['hello','leetcode'])

Expected Output: True

Explanation: Alien dictionary example.

Input: ('abcdefghijklmnopqrstuvwxyz', ['apple','app'])

Expected Output: False

Explanation: Prefix violation.

Hints

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.

Infer One Consistent Custom Alphabet

Given sorted words, infer one possible character order or return impossible.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

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

Expected Output: 'wertf'

Explanation: Classic ordering.

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

Expected Output: 'impossible'

Explanation: Invalid prefix.

Hints

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.

Loading coding console...