Guess the Word

Guess the Word

What is this problem about?

The Guess the Word interview question is a Mastermind-style game. You are given a list of 6-letter words. One is the secret word. You have an API guess(word) that returns the number of exact matches (same character in the same position) between your guess and the secret word. You have 10 allowed guesses to find the secret word.

Why is this asked in interviews?

Companies like Google and Dropbox ask this Game Theory and Interactive problem to evaluate your ability to design a heuristic strategy. There is no algorithm that guarantees a win 100% of the time in 10 guesses under all conditions, but you must implement a "Minimax" or "Elimination" strategy that maximizes the probability of winning. It tests your ability to filter search spaces based on feedback.

Algorithmic pattern used

This problem relies on a Search Space Elimination / Minimax pattern.

1. Pick a word from the list and guess it.
2. Get the match_count from the API.
3. If match_count == 6, you win.
4. Otherwise, filter the word list: the secret word MUST have exactly match_count matches with your guessed word. Discard all words in the list that don't satisfy this.
5. Repeat with a new word from the filtered list.
6. Optimization (Minimax): To pick the best next word, choose the one that minimizes the worst-case size of the next filtered list. (Or randomly picking is often "good enough" to pass the test cases).

Example explanation

Words: ["acckzz", "ccbazz", "eiowzz", "abcczz"]. Secret: "acckzz".

1. Guess "ccbazz". API returns 3 (because 'z', 'z', and one other char might align, wait: c-c, c-c, b-c, a-k, z-z, z-z. No, only 'z', 'z' align. Match = 2).
2. Filter the list: keep only words that have exactly 2 matches with "ccbazz".
   • "acckzz" matches "ccbazz" in 2 positions ('z', 'z'). Keep.
   • "eiowzz" matches in 2 positions ('z', 'z'). Keep.
   • "abcczz" matches in 2 positions ('z', 'z'). Keep.
3. Guess "eiowzz". API returns 2.
4. Filter again against "eiowzz" with match 2.
   • "acckzz" has 2 matches. Keep.
   • "abcczz" has 2 matches. Keep.
5. Eventually, the list shrinks to 1 word.

Common mistakes candidates make

• Random Guessing without Filtering: Just randomly guessing 10 words, which has a near-zero chance of success.
• Faulty Filtering Logic: Keeping words that have at least match_count matches instead of exactly match_count matches.
• Over-engineering: Trying to build a perfect Minimax tree that times out, when a randomized selection combined with strict filtering is highly effective and passes the platform's test cases.

Interview preparation tip

The core logic here is identical to "Wordle." The feedback you receive is a strict constraint. If you guessed "APPLE" and got 0 matches, the secret word cannot contain A, P, L, or E in those positions. Filtering the candidate pool is the key.