In-memory sentence index with add, remove and all-words search

Build an in-memory index over a collection of sentences. You can add sentences, remove them, and search for the sentences that contain every word of a query. Matching is by whole word and ignores case and punctuation.

Interface

Unless you agree on a different interface with the interviewer, assume:

• add(sentence_id: int, text: str) -> None — replaces the text if the id already exists.
• remove(sentence_id: int) -> bool — False if the id is unknown.
• search(query: str) -> list[int] — ids of sentences containing all of the query's words, ascending. An empty query returns [].
• Words are runs of letters and digits, lowercased.

Example

add(1, "The quick brown fox.")
add(2, "A quick brown dog!")
add(3, "Foxes are quick.")
search("quick brown")   ->  [1, 2]
search("FOX")           ->  [1]          # "Foxes" is a different word
search("quick")         ->  [1, 2, 3]
remove(2)
search("brown")         ->  [1]
add(1, "Slow turtle")
search("quick")         ->  [3]

Constraints

• Up to 10^5 sentences of up to 100 words; searches far outnumber updates.

Clarifying questions

• All words (AND) or any word (OR)?
• How are words split, and is matching case-insensitive?
• Should results be ranked or just listed?
• Prefix or partial-word matches?

What a strong answer covers

• An inverted index: word → set of sentence ids, plus id → its words so remove and replace are cheap.
• Search intersects the posting sets starting from the smallest.
• Tokenization in one place, used for both indexing and queries.
• Complexity of add, remove and search; memory for the postings.
• Tests for case, punctuation, replace, and a word that no longer appears anywhere.

Follow-ups

• Rank results by how many query words match, or by TF-IDF.
• Phrase search: words adjacent and in order (store positions).
• Prefix search for autocomplete.