Sparse Matrix-Vector Multiplication | Dataford Interview Questions

Implement an efficient sparse matrix times vector multiplication. Asked in the AI coding stage.

Write a function that takes a sparse matrix and a dense vector, then returns the product as a list of row sums. The matrix is represented as a list of rows, where each row is a list of [column_index, value] pairs for nonzero entries only.

Function Input

matrix: List[List[List[int]]]
vector: List[int]

Output

Return List[int] where result[i] is the dot product of row i with vector.

Constraints

0 <= len(matrix) <= 10^4
0 <= len(vector) <= 10^4
Each row contains only nonzero entries as [column_index, value] pairs
0 <= column_index < len(vector) for every entry
The total number of nonzero entries across all rows is at most 10^5
Values fit in 32-bit signed integers

Function Signature

def sparse_matrix_vector_multiply(matrix, vector):

Your question is Sparse Matrix-Vector Multiplication. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem