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.