Machine Coding: Word Search and Ordered Phrase Search Across a List of Documents

In a machine-coding round you are given a list of documents, where each document is a string of text identified by its position in the list. Build a small, well-structured search component over the list and implement two queries, in order. ### Clarifying Questions - What counts as a word: is matching case-insensitive, and how should punctuation and other separators be handled? - What should a query return: the matching document ids only, or also the positions or number of matches, and in what order? - Is the document list fixed once the component is built, or can documents be added or removed later? - Roughly how many documents and how much total text are there, and how often is each kind of query run? ### Part 1 — Find a word Implement `find_word(word)`, which returns the documents that contain the given word as a whole word. State the time and space cost of preparing the component and of each query. ```hint Pay once If the same document list is searched many times, think about what to precompute so that a query does not have to read every document again. ``` #### What This Part Should Cover - One tokenization rule, applied identically to documents and to queries, that matches whole words rather than substrings - The precomputed structure that maps a word to the documents containing it, and its build cost - Query cost, result ordering, and behavior for a word that appears nowhere ### Part 2 — Find a phrase Implement `find_phrase(phrase)`, which returns the documents in which the words of the phrase appear in the same sequence as in the phrase. ```hint What the word lookup loses A document can contain every word of the phrase without containing the phrase. Think about what to record for each occurrence of a word so that order can be checked without rescanning the text. ``` #### Clarifying Questions for this Part - Must the phrase's words be adjacent in the document, or only appear in the same order with other words allowed between them? - Can a phrase repeat a word, as in "to be or not to be", and must a match stay inside one sentence? #### What This Part Should Cover - The extra per-occurrence information the index keeps, and how a candidate document is verified against the phrase - How candidate documents are narrowed before verification - Correctness with repeated words, and the cost of a phrase query ### What a Strong Answer Covers - A clean interface that separates tokenizing, indexing and querying, so each piece can be tested and replaced - Whole-word semantics instead of substring matching, stated and handled consistently - Edge cases: an empty query, unknown words, words repeated within a document, and documents with no words - Build cost, query cost and memory of each structure, compared with scanning the documents for every query - Working code with a few concrete test cases that exercise the tricky inputs ### Follow-up Questions - How would you support adding and deleting documents after the index has been built? - How would you rank matching documents, for example by how often the phrase occurs? - If the index no longer fits in one machine's memory, how would you partition it, and what does a phrase query then cost? - How would you change Part 2 to find documents where the words appear within `k` positions of each other?