Quick Overview

This question evaluates string manipulation, multiset/frequency tracking, and stateful validation across rounds, with particular emphasis on handling repeated letters and multiplicity constraints in feedback generation.

Evaluate word-guess feedback with repeats

Company: Patreon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are implementing feedback for a Wordle-like guessing game. ## Part 1 — Produce feedback for one guess You are given two strings of equal length `guess` and `target` (lowercase letters). For each index `i`, output a status character: - `G` (green): `guess[i] == target[i]` - `Y` (yellow): `guess[i] != target[i]`, and the letter `guess[i]` occurs in `target` in some position **not already matched by a `G`**, respecting multiplicity (i.e., each occurrence in `target` can be used at most once across all `Y` assignments). - `W` (white/gray): otherwise. Return a string of length `n` over `{G,Y,W}`. ### Examples - `guess = "cable"`, `target = "maple"` → `WGWGG` - `guess = "paple"`, `target = "maple"` → `WGGGG` - `guess = "apple"`, `target = "maple"` → `YWGGG` ## Part 2 — Validate future guesses using past information Now the same `target` is used for multiple rounds. After each evaluated guess, you “learn” some letters are impossible. A future `guess` is considered **invalid_input** if it contains any letter that was previously confirmed to be absent from `target`. Clarification for repeated letters: a letter should be considered “confirmed absent” only if, in some previous round, **all** occurrences of that letter in that guess were marked `W` (i.e., the letter never appeared as `G` or `Y` in that round). ### Example Round 1: `guess = "cable"`, `target = "maple"` → `WGWGG` - Letters confirmed absent: `c`, `b`. Round 2: `guess = "cazle"`, `target = "maple"` → return `invalid_input` (contains `c`, which was confirmed absent). Implement the evaluator for Part 1 and the validator logic for Part 2. ## Constraints (reasonable assumptions) - `1 <= n <= 10^5` (design an efficient solution) - `guess.length == target.length` - Strings contain only lowercase English letters.

Overview: This question evaluates string manipulation, multiset/frequency tracking, and stateful validation across rounds, with particular emphasis on handling repeated letters and multiplicity constraints in feedback generation.

Read the full Patreon Software Engineer interview experience this question came from

Part 1: Produce feedback for one guess

Given two equal-length lowercase strings `guess` and `target`, return a feedback string of the same length. For each position: use `G` if the letters are equal, use `Y` if the guessed letter appears in some other unmatched position of `target`, and use `W` otherwise. Exact matches must be assigned first, and each occurrence in `target` can be used at most once across all `Y` assignments.

Constraints

  • 1 <= len(guess) == len(target) <= 100000
  • Both strings contain only lowercase English letters.

Examples

Input: ('cable', 'maple')

Expected Output: 'WGWGG'

Explanation: `a`, `l`, and `e` are exact matches. The remaining target letters are `m` and `p`, so `c` and `b` are both `W`.

Input: ('apple', 'maple')

Expected Output: 'YWGGG'

Explanation: After reserving the green `p`, `l`, and `e`, only one `a` remains available for yellow. The first `a` is `Y`, but the extra `p` becomes `W`.

Hints

  1. First mark every exact match as `G`. Those target positions cannot be reused for `Y`.
  2. Count only the letters from target that were not matched as `G`, then scan the remaining guess positions and assign `Y` while decrementing counts.

Part 2: Validate future guesses using past information

You are given a fixed lowercase `target` word and a list of `guesses`, all of the same length. Process guesses in order. A guess is `invalid_input` if it contains any letter that was previously confirmed absent from the target. Otherwise, evaluate it using Wordle-like feedback: `G` for exact match, `Y` for a letter that appears in another unmatched target position, and `W` otherwise. After evaluating a valid guess, a letter becomes confirmed absent if every occurrence of that letter in that guess received `W`. If a guess is invalid, it is not evaluated and it does not update the learned information. Return the result for every round.

Constraints

  • 1 <= len(target) <= 100000
  • 0 <= len(guesses)
  • Each guess contains only lowercase English letters and has length equal to len(target).
  • The sum of lengths of all guesses is at most 200000.

Examples

Input: ('maple', ['cable', 'cazle', 'zzzzz'])

Expected Output: ['WGWGG', 'invalid_input', 'WWWWW']

Explanation: After `cable`, letters `c` and `b` are confirmed absent. `cazle` is invalid because it contains `c`. Invalid guesses do not teach anything, so `zzzzz` is still evaluated normally.

Input: ('abca', ['aaaa', 'dada'])

Expected Output: ['GWWG', 'WYWG']

Explanation: In round 1, letter `a` is not confirmed absent because it has green positions. Therefore round 2 is valid even though it contains `a`.

Hints

  1. Keep a set or 26-length boolean array for letters already proven absent. Check that before evaluating each new guess.
  2. To decide which letters become absent after a valid round, look at each distinct letter in that guess: if none of its positions were marked `G` or `Y`, then that letter is confirmed absent.

Loading coding console...