Hashmap-Based Word Search | Dataford Interview Questions

Your question is Hashmap-Based Word Search. 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.

Problem

Apple Spotlight stores an inverted index mapping normalized words and phrases to document identifiers. Implement a search function that returns the document identifiers associated with a query.

The search must be case-insensitive and must treat consecutive whitespace characters as a single space. The index keys are already normalized using lowercase letters and single spaces. Preserve the document identifier order stored in the index.

Formal Specification

Implement search_index(index, query), where index is a dictionary mapping normalized strings to lists of document IDs, and query is a string. Return a new list containing the IDs for the normalized query, or an empty list if the query is not present. Do not modify index.

Constraints

1 <= len(index) <= 10^5
Each index key is a non-empty normalized word or phrase
The query may contain leading, trailing, or repeated whitespace
Document IDs are strings
Do not modify the input dictionary or its posting lists

Function Signature

def search_index(index, query):