Searching Engine
Challenge 1 - Hard
Description
Develop a simplified search engine that indexes sentences and allows users to query for sentences containing specific sets of words. The system should efficiently handle both storage and retrieval operations.
Functional Requirements:
- Insertion: Store a list of sentences, using an appropriate data structure. Each sentence is a string of lowercase English words, separated by spaces, without punctuation.
- Search: Retrieve sentences containing all words in a given list, irrespective of their order in the sentence.
Constraints:
- Maximum of 20 words per sentence.
- Potential for millions of sentences in the database.
- Up to 1000 unique words across all sentences.
- Sentences need not be grammatically correct (words can appear in any order).
- Insertions are mostly done during initialization, and search will be called frequently, primarily with exactly two words.
Example:
Given the sentences:
0
1
2
3
4
5
6
"mountain clean surface resort ways farm male"
"male surface hold wednesday window south"
"mr hold necessary wednesday justice saw parents"
"mr hold necessary thursday nights"
"connect richard sub players tour channel"
"publisher animals returns southern described"
A query for Insertion["hold", "wednesday"] should return:
0
1
2
"male surface hold wednesday window south"
"mr hold necessary wednesday justice saw parents"