Document Search: Exact Word Match, Non-Adjacent Phrase Match and AND/OR Queries

You are given a collection of documents, each with an integer id and its text. Build a search component over them. The interviewer adds requirements one at a time, so expect the queries to grow more complex as you go. The examples below use this collection: | id | text | | --- | --- | | 1 | the quick brown fox | | 2 | the lazy dog sleeps | | 3 | a quick dog chased a lazy fox | ### Constraints and Clarifications - The documents are known up front and many queries follow, so preprocessing them is allowed. - A query word matches only a whole word in a document: `do` does not match `dog`. - Results are lists of document ids in ascending order (an assumption of this version). ### Clarifying Questions - Is matching case-sensitive, and how should punctuation be treated when text is split into words? - Can documents be added, changed or removed between queries? ### Part 1 — Documents containing a word Return every document that contains a given word, as an exact match. For example, `fox` returns `[1, 3]` and `do` returns `[]`. ```hint Build once, query many times The same documents serve many queries. Think about what to compute once so that a query does not have to reread every document. ``` #### What This Part Should Cover - Splitting text into words, and the exact-match rule - A structure built once that answers each word lookup quickly - The cost of building it and of each query ### Part 2 — Documents containing a phrase whose words need not be adjacent Given a phrase of several words, return every document that contains the phrase, where the phrase's words do not have to be next to each other in the document. For example, `quick fox` returns `[1, 3]`, even though in neither document does `quick` come directly before `fox`. ```hint Reuse Part 1 Each word of the phrase already gives you a set of documents. Think about how to combine those sets cheaply, and what extra information you would need if word order turned out to matter. ``` #### Clarifying Questions for this Part - Must the words appear in the same order as in the phrase? For `lazy dog`, the answer is `[2, 3]` if order does not matter and `[2]` if it does, because document 3 has `lazy` only after `dog`. - If a word appears twice in the phrase, must it appear twice in the document? #### What This Part Should Cover - Combining the per-word results, and an evaluation order that keeps the work small - Handling the order-sensitive reading if the interviewer wants it - Words that appear in no document, empty phrases, and repeated words ### Part 3 — Words combined with AND and OR A query is now a sequence of words joined by `AND` or `OR`, such as `fox AND dog` or `fox OR sleeps`. Return every document that satisfies the query. For example, `fox AND dog` returns `[3]` and `fox OR sleeps` returns `[1, 2, 3]`. ```hint Agree on how the query reads Before writing code, settle how a mix of `AND` and `OR` groups, then map each operator onto an operation on sets of documents. ``` #### Clarifying Questions for this Part - Does `AND` bind more tightly than `OR`, or is the query read from left to right? `fox OR dog AND sleeps` returns `[1, 2, 3]` under the first reading and `[2]` under the second. - Can queries contain parentheses, and what should happen with a malformed query such as `fox AND` or `OR dog`? #### What This Part Should Cover - Parsing and validating the query - Mapping operators onto set operations with the agreed precedence - The cost of evaluation, and keeping intermediate results small ### What a Strong Answer Covers - An index built once, with stated build and query costs - Explicit clarification of ambiguous semantics (case, word order, operator precedence) before coding - Correct, tested code for each stage, extended rather than rewritten as requirements arrive - Edge cases: unknown words, empty queries, repeated words, malformed boolean queries - Awareness of how the design scales to many or large documents ### Follow-up Questions - How would you support exact phrase search, where the words must be adjacent and in order? - How would you add parentheses and a `NOT` operator? - Documents are added and deleted continuously. How do you keep the index current? - The collection grows to hundreds of millions of documents. How do you store the per-word document lists and intersect them efficiently?