Compute worst-case guesses for adaptive hangman
Company: Dropbox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a set of distinct lowercase words, all of the same length. A hidden word is chosen from this set, but the host is adversarial: after each of your letter guesses, the host may switch to any other word in the set as long as it remains consistent with every answer revealed so far.
On each turn, you guess one lowercase letter that you have not guessed before. The host then reveals the pattern for that letter with respect to some currently valid hidden word: every matching position is shown, or the host may report that the letter does not appear if there exists a consistent word without that letter.
Your goal is to guarantee identification of the hidden word in the worst case. Return the minimum number of letter guesses needed if you choose guesses optimally and the host responds adversarially.
You may assume the word is identified once only one candidate word remains consistent with all revealed patterns.
Quick Answer: This question evaluates algorithmic problem-solving, combinatorial reasoning, and adversarial information-theoretic thinking by requiring modeling of worst-case query strategies for adaptive letter-guessing.
Given equal-length candidate words, return the minimum number of distinct letter guesses needed to identify the word against an adversarial host.
Constraints
- words are distinct lowercase strings of the same length
- len(words) is small enough for minimax over states
Examples
Input: (['aa'],)
Expected Output: 0
Explanation: One candidate is already identified.
Input: (['ab', 'cd'],)
Expected Output: 1
Explanation: One distinguishing guess is enough.
Input: (['cat', 'car', 'bar'],)
Expected Output: 2
Explanation: The first guess can split but the host chooses the largest remaining group.
Input: (['aaa', 'bbb', 'ccc', 'abc'],)
Expected Output: 2
Explanation: Small adversarial partitioning case.
Hints
- Partition candidates by the revealed positions for a guessed letter.
- Use memoization on the candidate set and guessed letters.