Find a secret word via match feedback
Company: Moveworks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Word Guessing Game (Mastermind-style)
You are given a list of **unique** candidate words `wordlist`. All words have the same length `L` and contain only lowercase letters.
There is an unknown **secret** word that is guaranteed to be in `wordlist`. You can make a guess by choosing any word from `wordlist`. After each guess, you receive an integer `k` meaning:
- `k` = the number of positions `i` where `guess[i] == secret[i]` (exact position matches).
### Task
Design a strategy/function that finds the secret word using at most `G` guesses.
### Interface (conceptual)
- You can call `match(guess) -> int` to get the feedback `k`.
- You must output the secret word (or stop once identified).
### Constraints
- `1 <= |wordlist| <= 1000`
- `1 <= L <= 10`
- Maximum allowed guesses `G` (e.g., `G = 10`)
### Notes
- The interviewer may simulate `match()`.
- Your approach should be efficient enough to work within the guess limit.
Quick Answer: This question evaluates algorithmic search, pattern-matching, and information-elimination skills in an interactive Mastermind-style word-guessing scenario, testing string comparison and combinatorial reasoning under constrained feedback.
You are given a list of **unique** candidate words `wordlist`. Every word has the same length `L` and contains only lowercase letters. One of them is the hidden **secret** word.
You can probe the secret with a guess: `match(guess)` returns an integer `k` equal to the number of positions `i` where `guess[i] == secret[i]` (exact-position matches). Using this feedback you must identify the secret using a small number of guesses (at most `G`, e.g. `G = 10`).
To make the strategy testable here, the oracle is simulated for you: implement `findSecret(wordlist, secret)` which internally calls `match(guess) -> k` against the given `secret`, runs your guessing strategy, and **returns the secret word it identifies**.
**Approach.** Maintain the set of words still consistent with all feedback received. Repeatedly pick a guess that minimizes the worst-case number of remaining candidates (minimax over the feedback buckets), call `match`, and discard every candidate whose feedback against the guess differs from the observed value. When `match` returns `L`, you've found the secret. This keeps the guess count well within typical limits (≈ O(log n) probes for random wordlists).
**Return value:** the identified secret word.
Constraints
- 1 <= |wordlist| <= 1000
- 1 <= L <= 10 (all words share the same length)
- Words contain only lowercase letters and are unique
- The secret is guaranteed to be present in wordlist
- Maximum allowed guesses G (e.g. G = 10)
Examples
Input: (['abc', 'abd', 'aac', 'xyz'], 'abd')
Expected Output: 'abd'
Explanation: Words differ at one or two positions; elimination narrows to 'abd' within the guess budget.
Input: (['a'], 'a')
Expected Output: 'a'
Explanation: Singleton wordlist: the only candidate is the secret.
Hints
- After each guess you can throw away every word that would NOT have produced the same feedback as the secret did — only words consistent with all feedback can be the secret.
- Don't guess blindly: pick the guess whose feedback splits the remaining candidates most evenly. Concretely, for each candidate guess, bucket the other candidates by their match-score and choose the guess that minimizes the largest bucket (minimax).
- match(guess, candidate) is symmetric and cheap (compare characters position by position). Recompute it lazily while pruning.
- When match returns L (all positions match), the guess IS the secret — stop and return it.