Select next Hangman letter
Company: Moveworks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given the current state of a Hangman game, implement a function that selects the next letter with the highest likelihood of appearing in the secret word. Inputs:
(
1) the current pattern string showing revealed letters and placeholders (e.g., '_' for unknowns),
(
2) the set of letters already guessed (both correct and incorrect), and
(
3) a dictionary (word list). Compute the set of candidate words consistent with the pattern and excluding any letters known to be absent; then, among letters not yet guessed, choose the one that maximizes aggregate frequency across the candidate set. Clearly describe preprocessing of inputs, your algorithm, and time/space complexity. Specify and implement a deterministic tie-breaking policy for letters with equal frequency.
Quick Answer: This question evaluates algorithm design and string-processing skills, specifically pattern filtering, frequency analysis across candidate words, set operations for excluding guessed letters, deterministic tie-breaking, and complexity reasoning.
Given the current state of a Hangman game, choose the next letter to guess. The pattern string contains revealed lowercase letters and '_' for unknown positions. The guessed collection contains letters that have already been guessed, including both correct and incorrect guesses. The dictionary is a list of possible words.
Preprocess the inputs by converting letters to lowercase, converting guessed letters into a set, and treating any revealed pattern letters as already guessed. A dictionary word is a candidate if it has the same length as the pattern, matches every revealed position exactly, and has no already-guessed letter in any unknown position. This last rule excludes letters known to be absent and also prevents hidden extra copies of already-revealed letters.
After finding all candidate words, count the total occurrences of each not-yet-guessed letter across all candidates. Return the letter with the largest aggregate frequency. If multiple letters have the same maximum frequency, return the alphabetically smallest one. If there are no candidates or no useful unguessed letter appears, return the empty string.
Constraints
- 0 <= len(pattern) <= 30
- 0 <= len(dictionary) <= 50000
- Each dictionary word has length at most 30
- pattern contains only lowercase English letters and '_'
- guessed contains only lowercase English letters
- dictionary words contain only lowercase English letters
Examples
Input: ('_pp_e', {'p', 'e'}, ['apple', 'apply', 'ample', 'spore', 'angle'])
Expected Output: 'a'
Explanation: Only 'apple' matches the pattern. The remaining unguessed letters are 'a' and 'l', each with frequency 1, so the alphabetically smaller 'a' is chosen.
Input: ('_a__', {'a', 'e', 'r'}, ['ball', 'mass', 'taco', 'lava', 'warm', 'ally', 'beta'])
Expected Output: 'l'
Explanation: The candidates are 'ball', 'mass', and 'taco'. Words with hidden 'a', 'e', or 'r' in unknown positions are excluded. Frequencies include l=2 and s=2, so 'l' wins by alphabetical tie-break.
Hints
- When a pattern position is unknown, it cannot contain any letter that has already been guessed; otherwise that letter would either be revealed or known absent.
- You do not need to store all candidate words. Filter each word and update a 26-element frequency table as you go.