Implement sparse vector dot product and cosine similarity

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

Part 1: Sparse Vector Dot Product

You are given two sparse vectors. Each vector is represented by its full dimension and a dictionary of only its non-zero entries, where each key is a 0-based index and each value is the value at that index. Implement a function that returns the dot product of the two sparse vectors without iterating over every position from 0 to dim - 1. If the dimensions are different, return None.

Constraints

• 0 <= dim1, dim2 <= 10^9
• 0 <= len(values1), len(values2) <= 200000
• All keys in values1 are integers in [0, dim1 - 1].
• All keys in values2 are integers in [0, dim2 - 1].
• Dictionary values are floats and represent non-zero vector entries.
• The solution must not iterate over all dim positions.

Examples

Example 1

Input: (5, {0: 1.5, 3: 2.0}, 5, {1: 10.0, 3: 4.0})
Output: 8.0

Explanation: Only index 3 overlaps: 2.0 * 4.0 = 8.0.

Example 2

Input: (4, {0: 2.0, 1: 3.0}, 4, {2: 10.0})
Output: 0.0

Explanation: The vectors have no overlapping non-zero indices.

Hints

1. Only indices that appear in both sparse dictionaries can contribute to the dot product.
2. Iterate over the dictionary with fewer non-zero entries and look up each index in the other dictionary.

Part 2: Sparse Vector Cosine Similarity

You are given two sparse vectors. Each vector is represented by its full dimension and a dictionary of only its non-zero entries, where each key is a 0-based index and each value is the value at that index. Implement a function that returns the cosine similarity between the two sparse vectors. Cosine similarity is defined as dot(x, y) / (norm(x) * norm(y)). If the dimensions are different, return None. If either vector has zero norm, return 0.0.

Constraints

• 0 <= dim1, dim2 <= 10^9
• 0 <= len(values1), len(values2) <= 200000
• All keys in values1 are integers in [0, dim1 - 1].
• All keys in values2 are integers in [0, dim2 - 1].
• Dictionary values are floats and represent non-zero vector entries.
• The solution must not iterate over all dim positions.

Examples

Example 1

Input: (3, {0: 3.0, 1: 4.0}, 3, {1: 5.0})
Output: 0.8

Explanation: Dot product is 20. Norms are 5 and 5, so cosine similarity is 20 / 25 = 0.8.

Example 2

Input: (4, {0: 2.0}, 4, {3: 7.0})
Output: 0.0

Explanation: The vectors are orthogonal because they have no overlapping non-zero indices.

Hints

1. Compute the dot product using only overlapping non-zero indices.
2. The squared norm of a sparse vector is the sum of value * value over only its stored entries.