Live Coding Interview Prep

Course Content

Live Coding Interview Prep

7 sections · 50 lessons

Write code for a hybrid search system (keyword + vector search).

Fusing a BM25 ranking with a vector ranking210.03252130.03227320.03200BM25 rankvector rankRRF scoredoc 0doc 2doc 1Each rank r adds 1 divided by (60 + r); raw scores are never compared.
Doc 0 was never first in the keyword list, yet it wins because both retrievers put it near the top.

What you need to know

BM25 is the standard keyword-ranking formula used by Elasticsearch and OpenSearch. For each query term it rewards three things:

Text
score(doc) = sum over query terms t of             IDF(t) × f × (k1 + 1) / (f + k1 × (1 - b + b × len(doc) / avg_len))f       = how many times t appears in the doc (term frequency)IDF(t)  = log(1 + (N - n_t + 0.5) / (n_t + 0.5)), n_t = docs containing tk1=1.5  = how fast repeated terms stop adding score (saturation)b=0.75  = how much long documents are penalised

A rare term (high IDF) such as E4021 counts far more than a common one such as the. Repeating a term helps, but with diminishing returns.

Why fuse ranks, not scores. BM25 scores are unbounded (0, 3.7, 12.1…); cosine scores sit between -1 and 1. Adding them lets whichever retriever has the bigger numbers win. Reciprocal rank fusion (RRF) ignores the scores:

Text
RRF(doc) = sum over lists of 1 / (k + rank),   rank starts at 1, k = 60

A document ranked high in both lists beats one ranked first in only one list. k = 60 is the constant from the original RRF paper; it damps the gap between rank 1 and rank 2.

Python
import math, refrom collections import Counterimport numpy as npdef tokenize(text: str) -> list[str]:    return re.findall(r"[a-z0-9]+", text.lower())class BM25:    """Okapi BM25 over a small in-memory corpus."""    def __init__(self, docs: list[str], k1: float = 1.5, b: float = 0.75) -> None:        self.k1, self.b = k1, b        self.docs = [tokenize(d) for d in docs]        self.n = len(self.docs)        self.avgdl = sum(map(len, self.docs)) / self.n if self.n else 0.0        self.tf = [Counter(d) for d in self.docs]        df = Counter(t for d in self.docs for t in set(d))        self.idf = {t: math.log(1 + (self.n - f + 0.5) / (f + 0.5)) for t, f in df.items()}    def scores(self, query: str) -> np.ndarray:        out = np.zeros(self.n)        for term in tokenize(query):            idf = self.idf.get(term)            if idf is None:                continue                              # unseen term adds nothing            for i, counts in enumerate(self.tf):                f = counts[term]                if f:                    norm = 1 - self.b + self.b * len(self.docs[i]) / self.avgdl                    out[i] += idf * f * (self.k1 + 1) / (f + self.k1 * norm)        return out

The fusion and the search class:

Python
def reciprocal_rank_fusion(rankings: list[list[int]], k: int = 60) -> list[int]:    """Fuse ranked id lists; ids in more lists, higher up, come first."""    fused: dict[int, float] = {}    for ranking in rankings:        for rank, doc_id in enumerate(ranking, start=1):            fused[doc_id] = fused.get(doc_id, 0.0) + 1.0 / (k + rank)    return sorted(fused, key=fused.__getitem__, reverse=True)class HybridSearch:    """BM25 + embedding search, fused with RRF."""    def __init__(self, docs: list[str], embed_fn) -> None:        self.docs, self.embed_fn = docs, embed_fn        self.bm25 = BM25(docs)        self.matrix = None        if docs:            v = np.asarray(embed_fn(docs), dtype=np.float64)            self.matrix = v / (np.linalg.norm(v, axis=1, keepdims=True) + 1e-10)    def search(self, query: str, top_k: int = 5, pool: int = 20) -> list[str]:        if not self.docs:            return []        kw_scores = self.bm25.scores(query)        kw = [i for i in np.argsort(-kw_scores, kind="stable") if kw_scores[i] > 0][:pool]        q = np.asarray(self.embed_fn([query])[0], dtype=np.float64)        vec = np.argsort(-(self.matrix @ (q / (np.linalg.norm(q) + 1e-10))), kind="stable")        fused = reciprocal_rank_fusion([[int(i) for i in kw], [int(i) for i in vec[:pool]]])        return [self.docs[i] for i in fused[:top_k]]

Two details matter. The keyword list keeps only documents with a BM25 score above zero; otherwise every document that shares no word with the query still gets an RRF bonus just for appearing in the list. And the loops convert NumPy integers to plain int so the fused ids are ordinary dictionary keys.

Complexity: building BM25 is O(total tokens). This scan scores in O(q·N) for q query terms and N documents; an inverted index cuts it to the number of matching postings. Vector search is O(N·d). RRF is O(total list length) plus a sort of the fused ids.

A real-life example

Three documents from a payments help centre:

Python
docs = ["Error E4021 means the UPI PIN was wrong",        "Payment failed because the PIN was incorrect",        "Delivery is delayed by rain"]bm = BM25(docs)print(bm.scores("E4021").round(3))       # [0.9 0.  0. ]print(bm.scores("wrong PIN").round(3))   # [1.331 0.46  0.   ]

Trace for "E4021": the corpus has 20 tokens over 3 docs, so avg_len = 6.667. e4021 is in 1 doc, so IDF = log(1 + 2.5/1.5) = 0.981. Doc 0 has 8 tokens, so norm = 0.25 + 0.75 × 8/6.667 = 1.15, and the score is 0.981 × 1 × 2.5 / (1 + 1.5 × 1.15) = 0.9. An embedding model would put "E4021" close to any payment error; BM25 finds the one document that names it.

Now fuse a keyword ranking [2, 0, 1] with a vector ranking [0, 1, 2]:

dockeyword rankvector rankRRF score
02 → 1/621 → 1/610.03252
21 → 1/613 → 1/630.03227
13 → 1/632 → 1/620.03200

reciprocal_rank_fusion([[2, 0, 1], [0, 1, 2]]) returns [0, 2, 1]: doc 0 was never first in the keyword list, but it is near the top of both lists, and that is the kind of agreement RRF rewards.

Product search on an Indian marketplace needs both: "boAt Airdopes 141" must match that exact model (keyword), and "wireless earbuds under 1500" must match listings that never use those words (vector).

Follow-up questions to expect

  • "Why not a weighted sum like 0.7 × vector + 0.3 × BM25?" — It works only after you normalise both scores to the same range, and the right weight changes per query type. RRF needs no tuning; I'd try a weighted sum only if an eval shows it beats RRF.
  • "How would you do this in production?" — OpenSearch or Elasticsearch with a kNN field, or Postgres with tsvector full-text search plus pgvector, fusing in SQL or in the app.
  • "What about duplicates across the two lists?" — That is the point of the dictionary: a document found by both retrievers is one entry with two contributions. Exact duplicate documents should be removed at index time by content hash.