Implement sparse vector dot product and cosine similarity

Q: Implement sparse vector dot product and cosine similarity

This question evaluates implementation of sparse data structures and efficient algorithms for high-dimensional vector operations, specifically the dot product and cosine similarity, testing knowledge of sparsity-aware computation and linear algebra concepts such as vector norms.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Sparse Vector Class

Implement a SparseVector class for high-dimensional vectors where most entries are zero.

Representation

Assume each vector has:

dim: int (the full dimensionality, e.g., 1,000,000)
values: Map[int, float] storing only non-zero entries (index → value). Indices are 0-based and must be in [0, dim-1] .

Task 1 — Sparse vector multiplication (dot product)

Add a method (or standalone function) to compute the dot product between two sparse vectors:

dot(other: SparseVector) -> float
If self.dim != other.dim , return an error (e.g., raise an exception or return a special error value as specified by the interviewer).
Must be efficient for sparse data (avoid iterating over all dim entries).

Task 2 — Cosine similarity

Extend the same class with a method:

cosine_similarity(other: SparseVector) -> float
If dimensions don’t match, return an error.
Define cosine similarity as:

$\cos(\theta)=\frac{\mathbf{x}\cdot \mathbf{y}}{\|\mathbf{x}\|\,\|\mathbf{y}\|}$

Specify what you do if either vector has zero norm (e.g., return 0, or return an error).

Output/Expectations

Provide clean, readable code (any mainstream language is acceptable).
Briefly state time complexity in terms of number of non-zeros (nnz).