Find a secret word using match feedback
Company: Atlassian
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given a list of unique words, each with the same length (e.g., 6 lowercase letters). One of these words is the **secret**.
You can repeatedly make a guess by choosing a word from the list. After each guess, you receive feedback: the number of positions where your guessed word exactly matches the secret word (same character and same index).
## Task
Design an algorithm that finds the secret word within a limited number of guesses (e.g., at most 10), by choosing guesses adaptively based on feedback.
## Details
- Feedback is an integer from `0` to `L` where `L` is word length.
- After each guess, you may use the feedback to eliminate impossible candidate words.
## What to discuss
- How to pick the next guess to minimize the worst-case remaining candidates.
- Time complexity considerations for up to a few thousand words.
Quick Answer: This question evaluates algorithmic problem-solving, combinatorial reasoning, and information-theoretic search strategies for narrowing a secret from a candidate set using match-count feedback.