Find secret word with match-count feedback

Q: Find secret word with match-count feedback

This question evaluates algorithmic reasoning and inference from constrained feedback, testing skills in information-theoretic deduction, pattern matching, and search strategy within a bounded-query interactive setting.

Q: 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.

Q: What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

Q: What role is this question designed for?

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

Question

Find secret word with match-count feedback

PracHub · Accepted Answer

def solution(words, secret):
    if not words or secret not in words:
        return ""

n = len(words)
    L = len(words[0])

def exact_matches(a, b):
        return sum(ch1 == ch2 for ch1, ch2 in zip(a, b))

guesses_used = 0

def matchCount(guess):
        nonlocal guesses_used
        guesses_used += 1
        return exact_matches(guess, secret)

# Precompute pairwise match counts between every pair of words.
    match_matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            m = exact_matches(words[i], words[j])
            match_matrix[i][j] = m
            match_matrix[j][i] = m

candidates = list(range(n))
    used = set()

while candidates and guesses_used < 10:
        if len(candidates) == 1:
            guess_idx = candidates[0]
        else:
            candidate_set = set(candidates)
            best_idx = None
            best_worst_bucket = float("inf")
            best_is_candidate = False

for i in range(n):
                if i in used:
                    continue

buckets = [0] * (L + 1)
                for j in candidates:
                    buckets[match_matrix[i][j]] += 1

worst_bucket = max(buckets)
                is_candidate = i in candidate_set

if (
                    best_idx is None
                    or worst_bucket < best_worst_bucket
                    or (
                        worst_bucket == best_worst_bucket
                        and is_candidate
                        and not best_is_candidate
                    )
                ):
                    best_idx = i
                    best_worst_bucket = worst_bucket
                    best_is_candidate = is_candidate

guess_idx = best_idx

used.add(guess_idx)
        feedback = matchCount(words[guess_idx])

if feedback == L:
            return words[guess_idx]

candidates = [
            j for j in candidates
            if match_matrix[guess_idx][j] == feedback
        ]

return ""

Quick Overview

Examples

Solution

Hints

Quick Overview