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 Hudson River Trading.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Hudson River Trading during technical interviews.

Implement Wordle-style word guessing solver | Hudson River Trading Coding Question

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.

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

Input: (['wordy'], 'wordy', 6)

Expected Output: ('wordy', 1)

Explanation: One candidate is guessed and solved on attempt 1.

Input: ([], 'xxxxx', 6)

Expected Output: ('', 0)

Explanation: Empty dictionary returns empty guess and zero attempts.

Input: (['bat', 'cat', 'hat', 'mat', 'rat', 'sat'], 'rat', 1)

Expected Output: ('bat', 1)

Explanation: With max_attempts=1 on near-identical words, returns best guess after one attempt.

Input: (['dog', 'cat', 'pig', 'owl', 'fox', 'bee'], 'fox', 6)

Expected Output: ('fox', 2)

Explanation: Distinct-letter 3-word set converges to FOX.

Hints

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

Quick Overview