Top-K Similarity Search | Dataford Interview Questions

Handshake Search represents profiles or opportunities as fixed-length numeric vectors. Given a query vector and a large collection of candidate vectors, return the indices of the k most similar candidates using cosine similarity.

Use a bounded min-heap so the algorithm does not sort every candidate. Return indices in descending similarity order. If two candidates have equal similarity, return the smaller index first.

Formal Specification

Implement top_k_similar(vectors, query, k).

vectors is a list of n vectors, where each vector is a list of d numbers.
query is a length-d vector.
k is an integer between 1 and n.
Return a list of exactly k integer indices.
Similarity is dot(a, b) / (||a|| * ||b||).
All vectors, including query, have nonzero magnitude.

Constraints

1 <= k <= n <= 10^5
1 <= d <= 100
Every vector has exactly d numeric components
Every vector, including query, has nonzero magnitude
The output contains exactly k indices

Function Signature

def top_k_similar(vectors, query, k):

Your question is Top-K Similarity Search. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem