Your question is Search With Map of Lists. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Grammarly Editor needs a lightweight search feature that finds documents containing every word in a user query. Implement an inverted index using a map from each normalized word to a list of document IDs, then search that index efficiently.
Implement search_documents(documents, query). documents is a list of strings, where the index of each string is its document ID. query is a string containing one or more search terms. Normalize text by converting it to lowercase and treating every maximal sequence of letters or digits as one word. Return a sorted list of document IDs containing every distinct normalized query word. Return an empty list if any query word is absent or if the query contains no words.
Each posting list must contain each document ID at most once and remain sorted. You may build the index inside the function. Do not use substring matching, so edit does not match editor.
Example 1
Input: documents = ["Write clearly and confidently", "Confident writing takes practice", "Clear writing improves communication"], query = "clear writing"
Output: [2]
Document 2 contains both normalized words, while documents 0 and 1 contain only one of them.
Example 2
Input: documents = ["Grammar matters", "Grammar and clarity matter"], query = "GRAMMAR grammar"
Output: [0, 1]
Duplicate query terms are treated as one distinct word.
1 <= len(documents) <= 10^510^4 characters.10^6 characters.def search_documents(documents, query):