Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google SWE interview with a tricky interactive search problem. The core challenge was figuring out a strategy to find a secret word using at most 10 API calls, which sounds manageable until you actually sit down and think about worst-case pruning.

Questions Asked (1)

You have a list of unique same-length words and a hidden secret word. You can call an API that tells you how many character positions your guess matches the secret word exactly. Using at most 10 calls, find the secret word. Every guess must come from the word list.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I spent the first few minutes just staring at it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a constraint satisfaction or information-gathering task: each API call returns the exact match count, which partitions the candidate set. Use a strategy that maximizes information gain per guess, such as choosing a guess that splits the remaining candidates as evenly as possible, or using a precomputed decision tree if the word list is small. If the list is large, consider a two-phase approach: first narrow down using a few strategic guesses, then exhaustively search the reduced set.

Pro tip: Always clarify constraints (word list size, word length, API cost) before diving into an algorithm, and mention that you'd verify the solution with edge cases like all words matching or no matches. This shows you think about practical deployment and testing.

1. Clarify and formalize

Ask about the size of the word list, word length, and whether the API returns only the count or also positions. Formalize the problem as finding a target word from a set using queries that return the Hamming distance complement (exact matches).

2. Analyze information bounds

Calculate the maximum number of words that can be distinguished with 10 queries. Each query can return up to L+1 possible answers (0 to L matches), so 10 queries can distinguish at most (L+1)^10 words. If the list is larger, no strategy can guarantee success; if smaller, a decision tree may exist.

3. Design a strategy

For small lists, build a decision tree by recursively selecting a guess that partitions the remaining candidates into balanced subsets. For larger lists, use a greedy approach: pick a guess that maximizes the minimum partition size or entropy. Alternatively, use a known algorithm like Knuth's for Mastermind, adapted to exact matches only.

4. Handle worst-case and optimizations

If the list is too large for a perfect decision tree, propose a hybrid: use a few guesses to reduce the candidate set, then switch to exhaustive search. Discuss trade-offs between precomputation (building a decision tree) and online computation (greedy selection).

5. Test and validate

Walk through an example with a small word list, showing how the strategy narrows down candidates. Mention edge cases: secret word not in list (should not happen per problem), all words identical except one position, etc.

Key Points to Mention

Information theory: each query provides at most log2(L+1) bits, so 10 queries give at most 10*log2(L+1) bits, limiting the maximum distinguishable words.
Decision tree construction: recursively choose a guess that splits candidates into groups of roughly equal size based on match counts.
Greedy heuristic: at each step, pick the guess that minimizes the size of the largest resulting candidate subset (minimax).
Complexity analysis: time and space for precomputing partitions, especially if word list is large (e.g., O(N^2 * L) for all pairwise match counts).
Trade-offs: precomputation vs. online selection, and whether to guarantee worst-case 10 calls or optimize average case.
Practical considerations: API latency, caching results, and handling cases where no guess can reduce the candidate set (e.g., all remaining words have same match count to all guesses).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.