learn deep. ship safe.Practice testsFollow ByteMunSubscribe

mediumRAGRetrievalEmbeddings

Top-K Similar Documents

Return the indexes of the k document embeddings most similar to a query embedding, the core of the retrieval step in a RAG system, with a stable tie-break.

JavaScript or Python

The retrieval step of a RAG system embeds the user's question and finds the stored chunks whose embeddings are most similar. Given a query vector, a list of document vectors docs and an integer k, return the indexes of the k documents with the highest cosine similarity to the query, most similar first.

If two documents have exactly the same similarity, the one with the smaller index comes first. A zero vector has similarity 0 with everything. If k is larger than the number of documents, return all of them.

Examples

Example 1

Input: query = [1, 0], docs = [[0, 1], [1, 0], [1, 1]], k = 2
Output: [1, 2]
Why: Doc 1 is identical in direction (1.0); doc 2 is at 45 degrees (0.707)

Example 2

Input: query = [1, 1], docs = [[2, 2], [1, 1], [1, 0]], k = 2
Output: [0, 1]
Why: Docs 0 and 1 tie at 1.0; the smaller index wins

Constraints

  • 1 <= docs.length <= 10^4
  • 1 <= query.length == docs[i].length <= 1024
  • 1 <= k

Hints

Hint 1

Score every document with cosine similarity, keeping its index.

Hint 2

Sort by score descending, then index ascending, and take the first k.

Solution

Show the solution (try it yourself first)

Compute each document's cosine similarity with the query, pair it with its index, and sort by similarity (highest first) with the index as the tie-breaker. Slicing the first k handles a k larger than the list automatically.

def top_k_similar(query, docs, k):
    def cos(a, b):
        dot = sum(x * y for x, y in zip(a, b))
        na = sum(x * x for x in a) ** 0.5
        nb = sum(y * y for y in b) ** 0.5
        return 0.0 if na == 0 or nb == 0 else dot / (na * nb)
    scored = [(cos(query, d), i) for i, d in enumerate(docs)]
    scored.sort(key=lambda t: (-t[0], t[1]))
    return [i for _, i in scored[0:k]]

Complexity

Time O(n × d + n log n) for n documents of dimension d; a heap brings the selection to O(n log k). Space O(n). This brute-force scan is exact and fine for thousands of chunks; vector databases use approximate nearest-neighbour indexes such as HNSW to answer the same question over millions of vectors in milliseconds, trading a little recall for speed. That trade-off is a common follow-up question.

Found a mistake in this problem, its tests or the solution?

Written by Published Tests checked by Deepak
Case 1Input: [1,0], [[0,1],[1,0],[1,1]], 2Expected: [1,2]
Case 2Input: [1,1], [[2,2],[1,1],[1,0]], 2Expected: [0,1]

Run checks these 2 samples. Submit checks all 6 tests, including hidden ones.

  1. medium
  2. Cosine Similarity of EmbeddingsEmbeddings · Vectors
    easy
  3. Maximum Subarray SumArrays · Dynamic programming
    medium
  4. Longest Substring Without RepeatsStrings · Sliding window · Hash map
    medium