Katkat
Back

Build a Searchable Sentence Index

AmazonSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design an in-memory inverted index for text retrieval, requiring efficient tokenization, case-insensitive mapping, and dynamic updates to a collection of sentences.

Problem: Searchable Sentence Index

Design a class SentenceIndexer that maintains a collection of sentences and supports efficient keyword searching.

Implement the following methods:

  1. add_sentence(sentence_id: int, text: str) -> None: Adds a sentence to the index. Words should be tokenized (split by non-alphanumeric characters), converted to lowercase, and mapped to the sentence_id.
  2. remove_sentence(sentence_id: int) -> None: Removes the sentence from the index. Ensure all associated word references are cleaned up.
  3. search(query: str) -> List[int]: Returns a list of all sentence_ids that contain the given query word (case-insensitive). The list should be sorted by sentence_id in ascending order.

Constraints

  • text contains only alphanumeric characters and spaces.
  • Efficiency is critical: search should perform significantly better than a linear scan of all stored sentences.
  • sentence_id is a unique positive integer.

Example

indexer = SentenceIndexer()
indexer.add_sentence(1, "Hello world")
indexer.add_sentence(2, "Hello there")
indexer.add_sentence(3, "World of coding")

indexer.search("hello") # Returns [1, 2]
indexer.search("world") # Returns [1, 3]

indexer.remove_sentence(1)
indexer.search("hello") # Returns [2]

Edge Cases

  • Searching for a word not present in any sentence.
  • Removing a sentence_id that was never added.
  • Handling duplicate words within the same sentence (the index should only store the sentence_id once per word).

Hints

Hint 1

Use a hash map (dictionary) where keys are words and values are sets of sentence IDs containing those words.

Hint 2

For the removal operation, keep a secondary map that stores which words are associated with a specific sentence ID to avoid iterating through the entire inverted index.

Hint 3

Ensure that tokenization handles whitespace consistently and that your search returns results in sorted order.

Follow-up questions

  • How would you modify your solution to support prefix searches (e.g., searching for 'wor' returns results for 'world' and 'work')?
  • If the index size grows to exceed memory, what strategies would you use to store this index on disk?
  • How would you handle ranking results by frequency of the keyword appearing in the sentence rather than just presence?