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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

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

Find secret word with match-count feedback

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem You are given a list of **unique** lowercase words, all of the same length (e.g., length = 6). One of these words is a **secret** word. You can interact with a black-box API: - `matchCount(guess) -> int`: when you submit a word `guess` from the list, the API returns the number of positions `i` such that `guess[i] == secret[i]` (i.e., exact character match at the same index). You are allowed to call `matchCount` **at most 10 times**. ### Task Design/implement a function (e.g., `findSecretWord(words)`) that uses the API to identify the secret word within the guess limit. ### Notes / Constraints - `words` contains between 1 and 100 words. - All words have equal length `L` (commonly `L = 6`). - Every guess must be a word from `words`. - After each API response, you may adapt your next guess. ### What to return Depending on the interface, you may either: - return the identified secret word, or - stop once `matchCount(guess) == L` (found it). (Your interviewer may treat this as an interactive problem; focus on strategy + correctness under the 10-guess constraint.)

Quick Answer: 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.

You are given a list of unique lowercase words, and every word has the same length `L`. Exactly one word in the list is the secret word. In the original interview version, you interact with a black-box API: - `matchCount(guess) -> int` - It returns how many positions `i` satisfy `guess[i] == secret[i]` You may call this API at most 10 times, and every guess must be a word from the given list. In this non-interactive version, implement `solution(words, secret)` and simulate the API inside your function. The parameter `secret` is provided only so the judge can verify your strategy. Your function should repeatedly make guesses, use the returned match counts to eliminate impossible candidates, and return the discovered secret word. If your strategy does not find the secret within 10 guesses, return an empty string `""`.

Constraints

`1 <= len(words) <= 100`
`1 <= len(words[i]) <= 10`
All words are unique, lowercase, and have the same length `L`
`secret` is guaranteed to be one of the words in `words`
Your algorithm may use at most 10 simulated `matchCount` calls
Test data is designed so that a correct elimination strategy can identify the secret within the limit

Examples

Input: (["acckzz", "ccbazz", "eiowzz", "abcczz"], "acckzz")

Expected Output: 'acckzz'

Explanation: The secret is already one of the candidates. Using match-count feedback, the candidate set shrinks until `acckzz` is identified.

Input: (["secret"], "secret")

Expected Output: 'secret'

Explanation: With only one word in the list, the first allowed guess must be the secret.

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

Expected Output: 'b'

Explanation: This is a smallest-length edge case. Each guess returns either 0 or 1 exact matches, so the remaining candidates shrink immediately.

Input: (["wichbx", "oahwep", "tpulot", "eqznzs", "vvmplb", "eywinm", "dqefpt", "kmjmxr", "ihkovg", "trbzyb"], "eqznzs")

Expected Output: 'eqznzs'

Explanation: A partition-based strategy uses each feedback value to discard inconsistent words until `eqznzs` remains.

Solution

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 ""

Time complexity: O(n^2 * L + 10 * n^2), which simplifies to O(n^2 * L) for the given constraints. Space complexity: O(n^2).

Hints

After a guess returns `k`, any valid remaining candidate must also have exactly `k` matching positions with that guess.
A strong strategy is to choose the next guess that splits the remaining candidates as evenly as possible, minimizing the size of the largest feedback bucket.

Quick Overview

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.