Design a Search Ranking Algorithm Using Inverted Index

Problem Given a catalog of products, each with a name, tags and description, design a search system that returns products ranked by how well they match a free-text query.

Functional requirements

• Tokenize and index name, tags and description per product.
• Given a query, return matching products ranked by relevance, highest first.
• Support multi-token queries and partial matches.
• Weight fields differently (a name match beats a description match).
• Reflect catalog inserts/updates in search results.

Non-functional requirements

• ~10M products; average document ~1 KB → ~10 GB raw, ~15-20 GB indexed with positions.
• ~5k search QPS at peak; ~500 catalog updates/sec.
• Search p99 < 150 ms for the top-20 results.
• Index freshness: a catalog edit is searchable within ~1 s.
• Vocabulary ~2M unique terms after analysis.

Key components

• Analyzer: lowercase, strip punctuation, tokenize, remove stopwords, stem/lemmatize; the same analyzer must run at index time and query time or matches silently fail.
• Inverted index: token → posting list of (product_id, term_frequency, positions), plus per-term document frequency for IDF.
• Forward/doc-value store for the fields needed to score and render results.
• Scorer: TF-IDF or BM25 over matched terms, aggregated across fields with per-field boosts (name > tags > description).
• Top-K selection: a bounded min-heap over candidates rather than sorting all matches.
• In practice this maps directly onto Lucene/Elasticsearch: analyzers, per-field boosting, and BM25 out of the box.

Deep dives / trade-offs

• Raw term frequency vs TF-IDF vs BM25: counting matches alone means a product spamming a word in its description outranks an exact name match. IDF down-weights common catalog-wide tokens; BM25 adds saturation (the 10th occurrence of a word adds almost nothing) and length normalization (a long description shouldn't be penalized or rewarded purely for length). Explain why saturation matters concretely.
• Field weighting: score per field then combine (a weighted sum, or best-field/max), versus concatenating all fields into one blob and losing the ability to boost. Discuss why name should dominate.
• Posting list intersection: for multi-term AND queries, walk the shortest list first and skip-list into the others. This is what makes query latency depend on the rarest term, not the corpus size.
• Index updates: segments are immutable, so an update is a delete + re-add, with deletions tracked in a bitset and reclaimed at merge. This is the freshness-vs-throughput knob (refresh interval).
• Relevance beyond text: real ranking blends the text score with popularity, rating, recency and personalization — text relevance alone rarely wins. Mention learning-to-rank as the re-scoring layer over the top-N candidates.