Quick Overview

Implement Wordle-style word guessing solver evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement Wordle-style word guessing solver

Company: Hudson River Trading

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a program to solve a Wordle-style word guessing game. The game has a hidden target word of fixed length L (e.g., 5) drawn from a known dictionary. After each guess, you receive per-character feedback: Correct (right letter, right position), Present (letter exists but different position), or Absent (letter not in the word). Requirements: ( 1) Keep guessing until the word is solved or a maximum attempt limit is reached; ( 2) Design data structures and an algorithm to maintain constraints and prune the candidate set after each feedback; ( 3) Correctly handle repeated letters and seemingly conflicting feedback (e.g., one instance Present while another is Absent); ( 4) Propose and implement a strategy to choose the next guess (e.g., frequency-based heuristic or information-gain approximation) and justify it; ( 5) Provide an interface solve(dictionary, feedback_api, max_attempts) -> (final_guess, num_attempts) where feedback_api(guess) returns the feedback for each position; ( 6) Analyze time and space complexity; ( 7) Include unit tests and demonstrate a sample run.

Overview: Implement Wordle-style word guessing solver evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement a solver for a Wordle-style word-guessing game.\n\nA hidden `target` word of fixed length L is drawn from a known `dictionary` of equal-length lowercase words. For any guess you can derive per-character feedback:\n- **Correct (2)** — right letter, right position\n- **Present (1)** — letter is in the word but in a different position\n- **Absent (0)** — letter not in the word\n\nImplement `solve(dictionary, target, max_attempts)` returning `(final_guess, num_attempts)`:\n1. Repeatedly guess until the word is solved or `max_attempts` is reached.\n2. After each guess, prune the candidate set to every word that would produce the *same* feedback against the guess.\n3. Handle **repeated letters** correctly — the classic case where one instance of a letter is *Present* while a duplicate is *Absent*. Use a two-pass count: mark exact matches first, then consume remaining letter counts for misplaced letters.\n4. Choose the next guess with a **letter-frequency heuristic** (favor the candidate whose distinct letters cover the most remaining candidates), with a deterministic lexicographic tie-break.\n\n`final_guess` is the solved word if found within the limit, otherwise the last (best) guess; `num_attempts` is the number of guesses made. An empty dictionary returns `('', 0)`.

Constraints

  • All words in `dictionary` share the same length L.
  • Words are lowercase a-z.
  • `target` is the hidden word; for a solvable game it lies in `dictionary`.
  • 1 <= max_attempts; an empty dictionary returns ('', 0).
  • Repeated letters must be scored with exact Wordle semantics (two-pass count).

Examples

Input: (['crane', 'slate', 'trace', 'blink', 'ghost', 'lucky'], 'ghost', 6)

Expected Output: ('ghost', 2)

Explanation: Solver narrows to GHOST within the attempt limit.

Input: (['allee', 'apple', 'ample', 'amble', 'eagle', 'ladle'], 'apple', 6)

Expected Output: ('apple', 2)

Explanation: Target APPLE has duplicate P/L; repeated-letter scoring still converges.

Hints

  1. Write the feedback/scoring function first. Use TWO passes: pass 1 marks Correct (==2) positions and tallies the remaining (unmatched) letters of the target; pass 2 marks Present (==1) only while a remaining count for that letter is left. This is what makes 'one copy Present, another Absent' come out right.
  2. Pruning is the key insight: after guessing G and seeing feedback F, the target must be SOME word W in the candidate set for which score(G, W) == F. Filter the candidates to exactly those words — no other constraint bookkeeping is needed.
  3. For next-guess selection, count how many candidates contain each distinct letter, then pick the candidate maximizing the sum of those counts over its distinct letters. Break ties deterministically (e.g. lexicographically) so the run is reproducible.

Implement Wordle-style word guessing solver

mediumHudson River TradingSoftware Engineer

Implement a solver for a Wordle-style word-guessing game.\n\nA hidden target word of fixed length L is drawn from a known dictionary of equal-length lowercase words. For any guess you can derive per-character feedback:\n- Correct (2) — right letter, right position\n- Present (1) — letter is in the word but in a different position\n- Absent (0) — letter not in the word\n\nImplement solve(dictionary, target, max_attempts) returning (final_guess, num_attempts):\n1. Repeatedly guess until the word is solved or max_attempts is reached.\n2. After each guess, prune the candidate set to every word that would produce the same feedback against the guess.\n3. Handle repeated letters correctly — the classic case where one instance of a letter is Present while a duplicate is Absent. Use a two-pass count: mark exact matches first, then consume remaining letter counts for misplaced letters.\n4. Choose the next guess with a letter-frequency heuristic (favor the candidate whose distinct letters cover the most remaining candidates), with a deterministic lexicographic tie-break.\n\nfinal_guess is the solved word if found within the limit, otherwise the last (best) guess; num_attempts is the number of guesses made. An empty dictionary returns ('', 0).

View full question (all parts)

Implement Wordle-style word guessing solver

Implement a program to solve a Wordle-style word guessing game. The game has a hidden target word of fixed length L (e.g., 5) drawn from a known dictionary. After each guess, you receive per-character feedback: Correct (right letter, right position), Present (letter exists but different position), or Absent (letter not in the word). Requirements: (

  1. Keep guessing until the word is solved or a maximum attempt limit is reached; (
  2. Design data structures and an algorithm to maintain constraints and prune the candidate set after each feedback; (
  3. Correctly handle repeated letters and seemingly conflicting feedback (e.g., one instance Present while another is Absent); (
  4. Propose and implement a strategy to choose the next guess (e.g., frequency-based heuristic or information-gain approximation) and justify it; (
  5. Provide an interface solve(dictionary, feedback_api, max_attempts) -> (final_guess, num_attempts) where feedback_api(guess) returns the feedback for each position; (
  6. Analyze time and space complexity; (
  7. Include unit tests and demonstrate a sample run.

Clarifying Questions to Ask

  • Clarify input sizes, value ranges, mutability, return format, and tie-breaking.
  • State the target time and space complexity before coding.
  • Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes.

What a Strong Answer Covers

  • A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
  • A correctness argument that explains why the algorithm covers all required cases.
  • Time and space complexity, plus at least one alternative approach when relevant.
  • Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

  • How would the approach change if the input were streaming or too large for memory?
  • What invariants would you assert in production code?
  • Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Examples

Example 1
Input
(['crane', 'slate', 'trace', 'blink', 'ghost', 'lucky'], 'ghost', 6)
Output
('ghost', 2)
Notes
Solver narrows to GHOST within the attempt limit.
Example 2
Input
(['allee', 'apple', 'ample', 'amble', 'eagle', 'ladle'], 'apple', 6)
Output
('apple', 2)
Notes
Target APPLE has duplicate P/L; repeated-letter scoring still converges.

Constraints

  • •All words in `dictionary` share the same length L.
  • •Words are lowercase a-z.
  • •`target` is the hidden word; for a solvable game it lies in `dictionary`.
  • •1 <= max_attempts; an empty dictionary returns ('', 0).
  • •Repeated letters must be scored with exact Wordle semantics (two-pass count).

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def solve(dictionary: list[str], target: str, max_attempts: int) -> tuple[str, int]:
Sample call
solve(['crane', 'slate', 'trace', 'blink', 'ghost', 'lucky'], 'ghost', 6)
Language
Case 1
Input
(['crane', 'slate', 'trace', 'blink', 'ghost', 'lucky'], 'ghost', 6)
Expected
('ghost', 2)
Case 2
Input
(['allee', 'apple', 'ample', 'amble', 'eagle', 'ladle'], 'apple', 6)
Expected
('apple', 2)

Browse More Questions