Find documents containing all search query words
Filed under Amazon
Free read 1 of 3Handle fast multi-word intersection queries over a large document corpus.
The question
Given a large collection of N documents containing word lists and a query list of K words, output all document IDs that contain all K query words.
Constraints
- N can be large, requiring efficient indexing.
- K query words are distinct.
Examples
- Input
- Docs: {1: ['apple', 'banana'], 2: ['apple', 'banana', 'cherry']}, Query: ['apple', 'banana']
- Output
- [1, 2]
- Why
- Both documents contain both query words.
Approach
Handle fast multi-word intersection queries over a large document corpus.
Build an inverted index mapping each word to a posting list of document IDs. As noted by the interviewer, B-Trees or Tries can be used to store vocabulary terms and point to posting lists.
Retrieve posting lists for each of the K query words and compute their intersection.
Inverted index takes more storage upfront but speeds up query execution significantly compared to full scans.
Memory limits when posting lists are extremely large; handle via compression or skip pointers.
Tips
- What they are testing: Test with queries matching zero docs, single doc, and all docs.
- Common mistake: Iterating through all documents and checking word sets linearly without an inverted index or optimized structure.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.