Implement a Sparse Matrix Class

Problem Statement

In machine learning recommendation systems, interaction datasets (such as users saving Pins) are represented by massive, highly sparse matrices. Storing these matrices as dense 2D arrays is infeasible due to memory limits.

Design and implement a SparseMatrix class that efficiently stores non-zero entries and performs basic linear algebra operations without iterating over zero elements.

Implement the following methods:

• __init__(rows: int, cols: int): Initializes an empty matrix of dimensions rows x cols.
• set(r: int, c: int, val: float) -> None: Sets the value at (r, c). If val == 0, the entry should not occupy memory.
• get(r: int, c: int) -> float: Returns the value at (r, c), or 0.0 if it is not set.
• add(other: SparseMatrix) -> SparseMatrix: Returns a new SparseMatrix representing the sum of self and other. Raises ValueError if dimensions do not match.
• multiply(other: SparseMatrix) -> SparseMatrix: Returns a new SparseMatrix representing the product of self and other. Raises ValueError if self.cols != other.rows.

Class Interface

class SparseMatrix:
    def __init__(self, rows: int, cols: int):
        pass

    def set(self, r: int, c: int, val: float) -> None:
        pass

    def get(self, r: int, c: int) -> float:
        pass

    def add(self, other: 'SparseMatrix') -> 'SparseMatrix':
        pass

    def multiply(self, other: 'SparseMatrix') -> 'SparseMatrix':
        pass

Constraints

• 1 <= rows, cols <= 100,000
• Total non-zero entries per matrix nnz <= 100,000
• Values are floating-point numbers.
• Operations must only iterate over non-zero values.

Examples

Example 1: Addition

A = SparseMatrix(2, 2)
A.set(0, 0, 1.0)
A.set(1, 1, 3.0)

B = SparseMatrix(2, 2)
B.set(0, 0, 4.0)
B.set(0, 1, 2.0)

C = A.add(B)
# C is a 2x2 matrix:
# [5.0, 2.0]
# [0.0, 3.0]
assert C.get(0, 0) == 5.0
assert C.get(0, 1) == 2.0
assert C.get(1, 1) == 3.0
assert C.get(1, 0) == 0.0

Example 2: Multiplication

A = SparseMatrix(2, 3)
A.set(0, 0, 1.0)
A.set(0, 2, 2.0)

B = SparseMatrix(3, 2)
B.set(0, 1, 3.0)
B.set(2, 1, 4.0)

C = A.multiply(B)
# Dimensions: 2x2
# Row 0 of A dot Col 1 of B: (1.0 * 3.0) + (2.0 * 4.0) = 11.0
assert C.get(0, 1) == 11.0
assert C.get(0, 0) == 0.0

Edge Cases

• Setting an existing non-zero value to 0.0 should remove it from storage.
• Two non-zero elements summing to 0.0 during addition should not be stored in the result.
• Multiplying matrices where no corresponding non-zero elements align should result in an empty sparse matrix.