Semantic Search & Document QA
When you type a frustrated question into a help-center search box and the right article still comes back, something matched your words to documentation words. Retrieval is that step, and nearly every AI assistant runs it before answering: gather a handful of candidate documents, score each one against the question, rank the scores, and keep the winners under a reading limit. The scoring comes in two flavors. Keyword matching compares the literal words, using a family of scoring formulas called TF-IDF and its refinement BM25. Meaning matching converts text into vectors, long lists of numbers, then compares those lists with a similarity score called cosine similarity. The reading limit is counted in tokens, the word-sized pieces of text that models are billed and measured in. This matters because search quality bounds answer quality: an answer to a question whose source document was never fetched cannot exist. Interviewers like this topic because it is small, checkable math rather than a vocabulary test, and the classic request is to build all three steps in plain Python with no libraries. The three challenges below do exactly that: the cosine similarity number that orders meaning-based results, the TF-IDF formula that orders keyword results, and the packing step that keeps the selection under a token budget.
Key Concepts
- 1Cosine similarity is the score that orders meaning-based results: the question and each document become vectors (long lists of numbers), and the score is their dot product (multiply matching positions and add it up) divided by the product of the two lengths. Lists pointing the same direction score 1.0; lists sharing nothing score 0.0
- 2IDF down-weights common words: a term that appears in every document carries zero ranking signal, because matching it cannot help you pick one document out of the collection
- 3TF-IDF and BM25 score literal word matches, so neither retrieves a synonym unless the synonym actually appears in the document, and meaning-based search exists to cover that gap
- 4Token counts are estimates, at roughly 4 characters per token for English, and an overflowing prompt quietly loses its tail rather than raising an error
- 5Greedy first-fit, walking the candidates in order and keeping each one that still fits, is the baseline way to fill a token budget; picking better candidates is a retrieval problem, not a packing one