Implement feedback for word guessing game
Company: Dropbox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are implementing the core logic for a simple word-guessing game.
There is:
- A **dictionary** of valid words: a list of distinct lowercase strings, all of the same length `L`.
- A **secret** word: one of the words from the dictionary.
- A player's **guess** word.
For each guess you must return **feedback** consisting of:
- `exact_matches`: the number of positions `i` where `secret[i] == guess[i]`.
- `misplaced_matches`: the number of letters that appear in both `secret` and `guess` but **in different positions**, without double-counting any letter.
- If the guessed word is **not** in the dictionary, you should indicate it is invalid (for example, by returning a special value or throwing an error).
More formally:
- Let `secret` and `guess` be strings of length `L`.
- A character at index `i` contributes to `exact_matches` if `secret[i] == guess[i]`.
- After counting exact matches, remaining characters can contribute to `misplaced_matches`:
- For each distinct character `c`, count how many times `c` appears in the non-exact positions of `secret` and in the non-exact positions of `guess`.
- Add to `misplaced_matches` the minimum of those two counts.
### Requirements
Implement a function with the following behavior:
```text
get_feedback(dictionary: List[str], secret: str, guess: str) -> (int exact_matches, int misplaced_matches)
```
- If `guess` is not in `dictionary`, you may assume the function should signal an invalid guess in a clear way (e.g., by raising an exception or returning `(-1, -1)`).
- Otherwise, return the pair `(exact_matches, misplaced_matches)` as defined above.
You can assume:
- `1 <= len(dictionary) <= 10^5`
- All words in `dictionary`, and `secret` and `guess`, have the same length `1 <= L <= 20`.
- All words consist only of lowercase English letters `'a'`–`'z'`.
### Example
- `dictionary = ["apple", "angle", "ample"]`
- `secret = "apple"`
- `guess = "alley"` (this is in the dictionary or you may assume it is added for the example)
Then:
- Positions: `a p p l e` (secret)
- `a l l e y` (guess)
- `exact_matches = 1` (only the first `'a'` matches in the same position)
- Remaining letters:
- Secret has `p, p, l, e`
- Guess has `l, l, e, y`
- Common letters in different positions: `'l'` (1 time), `'e'` (1 time)
- So `misplaced_matches = 2`.
Design and implement an efficient algorithm to compute this feedback for a single guess.
Quick Answer: This question evaluates a candidate's ability to implement string-processing, frequency-counting, and membership-validation logic to generate exact and misplaced character matches for a word-guessing game.
You are implementing the core logic for a simple word-guessing game.
You are given:
- A **dictionary** of valid words: a list of distinct lowercase strings, all of the same length `L`.
- A **secret** word (one of the words from the dictionary).
- A player's **guess** word.
Implement `get_feedback(dictionary, secret, guess)` that returns a pair `[exact_matches, misplaced_matches]`:
- `exact_matches`: the number of positions `i` where `secret[i] == guess[i]`.
- `misplaced_matches`: the number of letters that appear in both `secret` and `guess` but in **different** positions, without double-counting any letter.
Formally:
- A character at index `i` contributes to `exact_matches` if `secret[i] == guess[i]`.
- After removing the exactly-matched positions, for each distinct character `c` count how many times `c` appears in the **non-exact** positions of `secret` and in the **non-exact** positions of `guess`; add the minimum of those two counts to `misplaced_matches`.
**Invalid guess:** If `guess` is not present in `dictionary`, signal an invalid guess. In this challenge, return `[-1, -1]`.
### Example
- `dictionary = ["apple", "angle", "ample", "alley"]`
- `secret = "apple"`, `guess = "alley"`
```
secret: a p p l e
guess: a l l e y
```
- `exact_matches = 1` (only index 0 `'a'` matches in place).
- Non-exact secret letters: `p, p, l, e`; non-exact guess letters: `l, l, e, y`.
- Common in different positions: `'l'` (min count 1) and `'e'` (min count 1) → `misplaced_matches = 2`.
- Result: `[1, 2]`.
Return `[exact_matches, misplaced_matches]`, or `[-1, -1]` if the guess is not in the dictionary.
Constraints
- 1 <= len(dictionary) <= 10^5
- All words in dictionary, secret, and guess have the same length L with 1 <= L <= 20
- All words consist only of lowercase English letters 'a'-'z'
- Words in the dictionary are distinct
- Return [-1, -1] when guess is not present in dictionary
Examples
Input: (["apple", "angle", "ample", "alley"], "apple", "alley")
Expected Output: [1, 2]
Explanation: Only index 0 'a' matches exactly (exact=1). Leftover secret p,p,l,e vs guess l,l,e,y share 'l' (1) and 'e' (1) in different positions, so misplaced=2.
Input: (["apple"], "apple", "apple")
Expected Output: [5, 0]
Explanation: Identical words: all 5 positions match exactly, no leftover letters, so misplaced=0.
Input: (["abcd", "dcba"], "abcd", "dcba")
Expected Output: [0, 4]
Explanation: A perfect anagram with no position matching: 0 exact, and all 4 letters match in different positions.
Input: (["aabb", "bbaa"], "aabb", "bbaa")
Expected Output: [0, 4]
Explanation: Repeated-letter anagram: 0 exact; leftover secret a,a,b,b vs guess b,b,a,a give min(2,2) for 'a' plus min(2,2) for 'b' = 4.
Input: (["abc", "xyz"], "abc", "xyz")
Expected Output: [0, 0]
Explanation: No shared letters: 0 exact and 0 misplaced.
Input: (["a"], "a", "a")
Expected Output: [1, 0]
Explanation: Single-character word that matches exactly.
Input: (["cat", "dog"], "cat", "god")
Expected Output: [-1, -1]
Explanation: Invalid guess: 'god' is not in the dictionary, so return [-1, -1].
Input: (["aabb", "abab"], "aabb", "abab")
Expected Output: [2, 2]
Explanation: Indices 0 ('a') and 3 ('b') match exactly (exact=2). Leftover secret a,b vs guess b,a give min for 'a' (1) and 'b' (1) = 2 misplaced.
Input: (["aaaa", "aaab"], "aaaa", "aaab")
Expected Output: [3, 0]
Explanation: First three 'a's match exactly (exact=3). Leftover secret 'a' vs guess 'b' share nothing, so misplaced=0 (no over-counting of repeated 'a').
Hints
- First scan both words position by position: whenever secret[i] == guess[i], increment exact_matches and exclude that position from later misplaced counting.
- For misplaced matches, tally the leftover (non-exact) letters of secret and of guess into two frequency maps, then for each letter add min(secret_count, guess_count). This prevents double-counting and handles repeated letters correctly.
- Validate the guess up front: put the dictionary in a hash set so membership is O(L); if the guess isn't there, return [-1, -1] immediately.