Top-K Similarity Search | Dataford Interview Questions

Your question is Top-K Similarity Search. Start with the requirements on the right.

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

Problem

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):