Longest Spoken Prefix with Repeated Words: Review an LCS Version, Then Rewrite It

A voice agent receives a script from a language model, `want_to_speak`, and produces a transcript of what it has actually said, `spoken_text`. The script is always correct. The transcript can contain repeated characters, repeated words or repeated word phrases, but speech only ever adds repetitions: the agent never skips or substitutes anything from the script. Return the longest prefix of `want_to_speak` that the agent has actually spoken. ```text want_to_speak: I can help you book an air ticket spoken_text: I can can help you book expected: I can help you book ``` ```text want_to_speak: I can help you book an air ticket spoken_text: I can can expected: I can ``` The round has two parts: first review a junior developer's implementation, then write your own version, `function_v2`. ### Clarifying Questions - Should the comparison be done word by word or character by character, given that a repetition can be a single stuttered character inside a word? - If the transcript ends in the middle of a word, does the partial word count as spoken? - Must case, punctuation and spacing match exactly, and should the result keep the script's original spacing? - What should happen when the script itself contains an immediately repeated word or phrase, such as "that that"? ### Part 1 — Review the LCS-based implementation The junior developer computes the longest common subsequence (LCS) of the two strings: a dynamic-programming table gives the LCS length, and the LCS is then rebuilt by walking the table from the bottom-right corner back to the start. The original code was not shared; the version below is a reconstruction of the described approach with the same two kinds of defect. Review it as you would a pull request. ```python def function_v1(want_to_speak: str, spoken_text: str) -> str: n, m = len(want_to_speak), len(spoken_text) dp = [[0] * m for _ in range(n)] for i in range(1, n + 1): for j in range(1, m + 1): if want_to_speak[i - 1] == spoken_text[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # Rebuild the LCS from right to left. i, j, out = n, m, [] while i > 0 and j > 0: if want_to_speak[i - 1] == spoken_text[j - 1]: out.append(want_to_speak[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] >= dp[i][j - 1]: i -= 1 else: j -= 1 return "".join(reversed(out)) ``` Even once it stops crashing, this approach returns `"I can an"` for the second example instead of `"I can"`. ```hint Run it in your head Compare the table's size with the largest indices the loops touch. Then trace the second example and ask where in `want_to_speak` the final "an" of the wrong output comes from. ``` #### What This Part Should Cover - The indexing defect: what fails, on which inputs, and the fix - Why a longest common subsequence is not the longest spoken prefix, shown on the failing example - The time and memory cost of the table for long scripts and transcripts - Which tests would have caught both defects before review ### Part 2 — Implement `function_v2` Write `function_v2(want_to_speak: str, spoken_text: str) -> str` so that it returns the expected output for both examples above and relies on the guarantee that speech only adds repetitions. State its time and memory cost. ```hint Read the guarantee again If nothing is ever skipped or substituted, ask what it can mean when the next piece of the transcript differs from the next piece of the script you are waiting for. ``` #### What This Part Should Cover - A solution that exploits the repetition-only guarantee instead of a general alignment - The unit of comparison, and how stuttered characters inside a word are treated - Output that matches the examples exactly, including no trailing space - Inputs on which the chosen rule could still be fooled, and what you would ask about them ### What a Strong Answer Covers - Reads the problem statement closely and turns the repetition-only guarantee into the algorithm - Finds both defects in the review and explains them with a concrete trace - Time and memory analysis for both versions, with a rewrite that is asymptotically cheaper than the table - Tests for both examples, a repetition at the very start or end, an empty transcript, a transcript equal to the script, and a stutter inside a word - Names the remaining ambiguities and asks about them instead of guessing silently ### Follow-up Questions - The transcript arrives in small chunks while the agent is speaking. How do you keep the answer current without rescanning from the start? - The script is "I said that that is fine" and the agent says it exactly. What does your function return, and what if the agent had said "that" three times? - If the speech recognizer could also drop or mishear words, which approach would you switch to, and what would it cost? - The user interrupts the agent mid-sentence. How would the spoken prefix be used in the conversation that follows?