Compute top-k cosine similarity over a large set of vectors without a vector database. Make it fast enough.

How to answer

“Fast enough” is a number the interviewer has and you don’t yet. Get it, make exact search fast, and say where exact stops being enough.

1. Ask for the sizes and the budget. How many vectors, what dimension, how many queries at once, what k, what latency target. Do the memory arithmetic aloud: n * d * 4 bytes in float32 tells you whether the corpus fits in memory.
2. Normalize the corpus once, when you build the index. Then cosine similarity is a dot product. Reject zero vectors, whose cosine is undefined. Normalizing the query changes the scores, not the ranking; say so.
3. Score with a matrix multiply. Stack the queries into a matrix and let one BLAS call score a block of the corpus against all of them. No Python loop over vectors.
4. Select, don’t sort. np.argpartition finds the top k in linear time, then sort only those k. In plain Python, heapq.nlargest keeps a heap of size k: O(n log k).
5. Block over the corpus to bound memory. Score one block, keep its top k, merge with the running top k. The score matrix never exceeds queries times block size.
6. State the complexity, then prove it right. Scoring is O(q * n * d) and dominates the operation count; selection is O(q * n), but BLAS can make the multiply faster than the selection, so time both. Check against a brute-force full sort on small random data first.
7. Say when to stop. If exact search misses the budget, go approximate (quantized vectors, clustering or a graph index from a library) and measure recall against the exact results you just built.

The trap is a full argsort of every score. Measure it: it can cost more than the multiply that produced the scores.