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 Technical Screen rounds at Moveworks.

What role is this question designed for?

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

Select next Hangman letter | Moveworks Coding Question

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.

Input: ('__', [], ['ab', 'ba'])

Expected Output: 'a'

Explanation: Both words are candidates. 'a' and 'b' each occur twice, so the alphabetically smaller letter 'a' is returned.

Input: ('a__a', {'a'}, ['alga', 'anna', 'area', 'abca', 'aaaa'])

Expected Output: 'n'

Explanation: 'aaaa' is invalid because already-guessed 'a' appears in unknown positions. Among the valid candidates, 'n' appears twice in 'anna', more than any other unguessed letter.

Input: ('a__', {'a', 'b'}, ['bbb', 'ccc', 'def'])

Expected Output: ''

Explanation: No dictionary word is consistent with the revealed leading 'a', so there is no useful guess.

Input: ('cat', {'c', 'a', 't'}, ['cat', 'car', 'cut'])

Expected Output: ''

Explanation: The word is already fully revealed. Even though 'cat' is a candidate, no unguessed letter appears in it.

Input: ('_____', {'e', 's'}, ['apple', 'berry', 'civic', 'cocoa', 'daddy', 'tests'])

Expected Output: 'c'

Explanation: Words containing already-guessed absent letters 'e' or 's' are excluded. The candidates are 'civic', 'cocoa', and 'daddy'. Letter 'c' appears 4 times, the highest aggregate frequency.

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.

Quick Overview

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.