Pairwise Cosine Similarity in NumPy

EasyML Coding

Reported in interviews at Amazon

Problem statement

A retrieval service stores document embeddings as rows of a matrix and needs to score a batch of query embeddings against all of them. Implement cosine similarity in NumPy for that setting.

A is an $m \times d$ nested list (one query vector per row) and B is an $n \times d$ nested list (one document vector per row). Return the $m \times n$ matrix $S$ with

$$S_{ij} = \frac{a_i \cdot b_j}{\lVert a_i \rVert_2 \, \lVert b_j \rVert_2}$$

If either vector has zero norm, define $S_{ij} = 0.0$; the output must never contain NaN or inf. Use vectorized NumPy rather than a Python loop over pairs. Return plain nested lists (a NumPy array is converted for you). Results are compared with a relative tolerance of $10^{-6}$, so you do not need to clip to $[-1, 1]$.

def cosine_similarity(A: list, B: list) -> list:
    ...

Constraints

  • $1 \le m, n \le 200$
  • $1 \le d \le 256$
  • every entry is in $[-100, 100]$

Example 1

A = [[1, 0], [1, 1]]
B = [[1, 0], [0, 1], [-1, -1]]
-> [[1.0, 0.0, -0.7071], [0.7071, 0.7071, -1.0]]   (rounded for display)

The second query points at 45 degrees, so it is equally similar to both axes and exactly opposite to $(-1, -1)$.

Example 2

A = [[0, 0, 0]]
B = [[1, 2, 3]]
-> [[0.0]]

A zero vector has no direction, so its similarity is defined as 0.0.

Example 3

A = [[3, 4]]
B = [[6, 8], [-4, 3]]
-> [[1.0, 0.0]]

$(6, 8)$ is a scaled copy of $(3, 4)$; $(-4, 3)$ is orthogonal to it.

Show hint

Can every pairwise similarity be read off one matrix product if the vectors are prepared the right way first?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems