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 Technical Screen rounds at Dropbox.

What role is this question designed for?

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

Build a hit/miss word guessing game | Dropbox Coding Question

Build a hit/miss word guessing game

Company: Dropbox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Two players play a word guessing game. - Player A chooses a **secret word**. - Player B repeatedly guesses **single letters**. - After each guess, the game reports: - **hit** if the secret word contains the guessed letter, and all occurrences of that letter are revealed in the current pattern - **miss** otherwise, and the letter is added to a `misses` list The interviewer will provide an example interaction to confirm behavior. ## Part 1 — Implement the game engine Design and implement data structures and functions to support: - Initializing a game with a secret word - Processing a guessed letter and returning updated state - Tracking revealed letters (e.g., pattern like `_ _ a _ a`) - Tracking missed letters (in insertion order) ### Inputs/Outputs (one possible shape) - Input: `secretWord`, then a sequence of guessed letters - Output after each guess: `{ result: "hit"|"miss", pattern, misses }` ## Part 2 (Follow-up) — Secret word may change mid-game Now Player A is allowed to **change the secret word during the game**, as long as it remains consistent with all previous responses (hits/misses and revealed pattern). Player B wants to **minimize the number of guesses** needed to fully determine the word. Discuss an approach and write high-level pseudocode for the strategy Player B should use. Assumptions you may make (state clearly): - There is a known dictionary/set of candidate words of the same length. - Only letter guesses are allowed (no full-word guesses), unless you explicitly add that rule. - Letters may or may not be repeated in guesses (specify behavior).

Quick Answer: This question evaluates implementation skills in managing stateful systems and data structures for pattern matching, as well as algorithmic and adversarial reasoning about information gain and search strategies when the secret can change.

Part 1: Hit/Miss Word Guessing Game Engine

Implement the core engine for a two-player word guessing game. Player A chooses a secret word, and Player B guesses one lowercase letter at a time. After each guess, return whether the guess was a hit or miss, the current revealed pattern, and the missed letters so far. A guess is a hit if the guessed letter appears anywhere in the secret word. All occurrences of a hit letter are revealed. A guess is a miss otherwise, and the letter is added to the misses collection in insertion order. To keep the output simple and cross-language friendly, each game state should be returned as a 3-element list: [result, pattern, misses]. Repeated guesses are allowed. Repeating a hit returns "hit" and does not change the pattern. Repeating a miss returns "miss" and does not add a duplicate letter to misses.

Constraints

0 <= len(secret_word) <= 10^4
0 <= len(guesses) <= 10^4
Each guess is a single lowercase English letter.
secret_word contains only lowercase English letters.
Repeated guesses are allowed but should not duplicate missed letters.

Examples

Input: ("banana", ["a", "x", "n", "b", "z"])

Expected Output: [["hit", "_a_a_a", ""], ["miss", "_a_a_a", "x"], ["hit", "_anana", "x"], ["hit", "banana", "x"], ["miss", "banana", "xz"]]

Explanation: The guesses reveal all occurrences of hit letters. Misses are tracked in insertion order.

Input: ("apple", ["p", "x", "p", "x", "e"])

Expected Output: [["hit", "_pp__", ""], ["miss", "_pp__", "x"], ["hit", "_pp__", "x"], ["miss", "_pp__", "x"], ["hit", "_pp_e", "x"]]

Explanation: Repeated guesses do not change the state or duplicate misses.

Input: ("", ["a", "b"])

Expected Output: [["miss", "", "a"], ["miss", "", "ab"]]

Explanation: An empty secret word contains no letters, so every guess is a miss.

Input: ("code", [])

Expected Output: []

Explanation: With no guesses, there are no states to return.

Input: ("a", ["b", "a"])

Expected Output: [["miss", "_", "b"], ["hit", "a", "b"]]

Explanation: A single-letter word starts fully hidden and is revealed after the correct guess.

Hints

Precompute the positions where each letter appears in the secret word.
Maintain a mutable pattern, such as a list of characters, and join it when producing each output state.

Part 2: Minimum Worst-Case Letter Guesses Against an Adaptive Secret Word

Player A is now allowed to change the secret word during the game, as long as every response remains consistent with some word from a known dictionary. Player B knows the dictionary and wants a strategy that guarantees identifying the exact word using as few letter guesses as possible in the worst case. All candidate words have the same length. When Player B guesses a letter, the response is the full position mask of that letter in the current secret word. For example, guessing 'a' against "banana" reveals positions 1, 3, and 5. The adaptive Player A may choose any nonempty group of remaining candidate words that share the same response mask, and will choose the group that maximizes the number of future guesses needed. Compute the minimum number of letter guesses Player B needs to guarantee determining the exact word in the worst case. Repeated guesses are not useful and should not be used. If the dictionary is empty, return -1.

Constraints

0 <= len(candidate_words) <= 14
0 <= len(candidate_words[i]) <= 12
All nonempty candidate words have the same length.
Words contain only lowercase English letters.
Only single-letter guesses are allowed; no full-word guesses are allowed.

Examples

Input: ([],)

Expected Output: -1

Explanation: There is no possible secret word to identify.

Input: (["planet"],)

Expected Output: 0

Explanation: With exactly one candidate word, the word is already determined.

Input: (["cat", "car", "dog"],)

Expected Output: 2

Explanation: One optimal first guess is 'c', separating dog from cat/car. If cat/car remain, one more guess distinguishes them.

Input: (["aa", "ab", "ba", "bb"],)

Expected Output: 1

Explanation: Guessing 'a' gives four different position masks, uniquely identifying all four words.

Input: (["abc", "abd", "abe"],)

Expected Output: 2

Explanation: Any useful guess can isolate at most one of the three words, so two guesses are needed in the worst case.

Hints

A guessed letter partitions the current candidate set by the exact positions where that letter appears.
Use minimax dynamic programming: Player B chooses the letter minimizing the worst remaining candidate group, while adaptive Player A chooses the worst group.

Quick Overview

This question evaluates implementation skills in managing stateful systems and data structures for pattern matching, as well as algorithmic and adversarial reasoning about information gain and search strategies when the secret can change.