How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Moveworks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Moveworks during technical interviews.

Find a secret word via match feedback | Moveworks Coding Question

Q: Find a secret word via match feedback

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.

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.

Input: (['cat', 'cot', 'cut', 'cog', 'dog'], 'dog')

Expected Output: 'dog'

Explanation: Several words share a common prefix/suffix; feedback buckets separate them.

Input: (['hello', 'jelly', 'jolly', 'belly', 'hilly'], 'jolly')

Expected Output: 'jolly'

Explanation: Length-5 words that pairwise differ in only a couple of positions, stressing the elimination logic.

Input: (['aaaa', 'aaab', 'aaba', 'abaa', 'baaa'], 'aaba')

Expected Output: 'aaba'

Explanation: All candidates are one position away from 'aaaa'; the minimax guess still isolates the secret.

Input: (['zz', 'zy', 'yz', 'yy'], 'yy')

Expected Output: 'yy'

Explanation: Length-2 boundary: every combination of two letters; feedback of 0 from 'zz' pins the answer.

Input: (['abcde', 'fghij', 'klmno', 'pqrst', 'uvwxy'], 'abcde')

Expected Output: 'abcde'

Explanation: Fully disjoint words: the secret is the only word giving a positive match against itself.

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.

Quick Overview

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.