Look Up a Book Title Typed with Missing or Extra Spaces

A library holds a list of book titles. Given a title typed by a user, decide whether that title is in the library. The typed title may have extra spaces, splitting a word in two, or missing spaces, running two words together, so a plain string comparison fails. The interviewer constrained the approach in two ways, and both are part of the problem: - Normalizing the library by deleting every space from each title and then comparing was not accepted. - Building an index over the words that appear in the library's titles was accepted as the starting point. What remains is matching the typed string against the words in that index when the typed spaces cannot be trusted. This was a 30-minute whiteboard question, and the code did not need to compile. An illustration (assumed data, not from the report): ```text library: "war and peace", "the old man and the sea", "dune" typed "warand peace" -> in the library (a missing space) typed "war an d peace" -> in the library (an extra space) typed "peace and war" -> depends on the matching rule; see the clarifying questions ``` ```hint Where can the first word end? Set the typed spaces aside and look at the characters alone. Ask which prefixes are words in the index; each one leaves a shorter version of the same question. ``` ```hint Do not solve the same suffix twice Different ways of splitting the start of the string can leave the same remaining characters. Decide what to remember so that each remaining suffix is examined only once. ``` ### Constraints and Clarifications - Only spacing is wrong: the typed title has the right characters in the right order, with no misspelled letters. - Not reported: the size of the library, how long titles are, and how letter case and punctuation are treated. Ask, or state your assumptions. ### Clarifying Questions - Is a typed string a match when it splits into the words of one particular title, in order, or when every piece is a word that appears somewhere in the index? The third example separates the two. - Should matching ignore letter case and punctuation? - Should the lookup return only yes or no, or the matching title, and what if two titles differ only in their spacing? - Is the library fixed and queried many times, so that indexing it once is worthwhile? ### What a Strong Answer Covers - Pins down the matching rule with a concrete example before coding - A word index built once from the library, with case and punctuation normalized the same way for titles and queries - Splitting the typed string into indexed words, with memoization so the search is not exponential, and the resulting complexity - Confirming the recovered words against real titles when the matching rule requires it - Edge cases: empty input, a word that is a prefix of a longer word, repeated words, titles that differ only in spacing ### Follow-up Questions - Return every title the typed string could match. How does the search change? - Users also make small typos inside words. How would you extend the matching? - The library holds millions of titles and queries arrive constantly. What would you precompute, and what would it cost in memory? - What does deleting all spaces from the library titles get right and wrong compared with your approach, and when would you accept it?