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.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Apple during technical interviews.

Implement sparse vector dot product and cosine similarity

Quick Overview

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.

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

Quick Overview

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

Implement sparse vector dot product and cosine similarity

Quick Overview

Sparse Vector Class

Representation

Task 1 — Sparse vector multiplication (dot product)

Task 2 — Cosine similarity

Output/Expectations

Comments (0)

Implement sparse vector dot product and cosine similarity

Quick Overview

Sparse Vector Class

Representation

Task 1 — Sparse vector multiplication (dot product)

Task 2 — Cosine similarity

Output/Expectations

Comments (0)