Sparse Matrix Left- and Right-Multiply Vector

Requirements

• Build a SparseMatrix type that records only entries whose values are non-zero.
• Provide multiplication in both orientations: M · v, where v is a column vector, and $v^{T} \cdot M$, where $v^{T}$ is a row vector.
• Each multiplication must run in O(nnz), where nnz is the number of stored non-zero elements, rather than scanning all rows · cols positions.

Use this interface:

class SparseMatrix:
    def __init__(self, rows: int, cols: int): ...
    def set(self, row: int, col: int, value: int) -> None: ...
    def right_multiply(self, vector: list[int]) -> list[int]: ...
    def left_multiply(self, vector: list[int]) -> list[int]: ...

set should replace the value at the specified coordinate; assigning zero should remove that coordinate from the sparse representation.

Notes

• Establish the row-versus-column vector conventions before coding.
• Account for incompatible dimensions, vectors that contain zero values, and possible integer overflow when dot products become large.

Preparation

• Be ready to explain the representation you selected and why it supports both multiplication directions.
• Be prepared to discuss the memory and cache implications of your design.

Examples

Example 1

Input:
M = 2 × 3 matrix with:
  M[0][1] = 4
  M[1][0] = 2
  M[1][2] = -1
v = [3, 5, 2]
M.right_multiply(v)

Output:
[20, 4]

The first result is 4·5 = 20, while the second is 2·3 + (-1)·2 = 4.

Example 2

Input:
M = 2 × 3 matrix with:
  M[0][1] = 4
  M[1][0] = 2
  M[1][2] = -1
v = [2, 3]
M.left_multiply(v)

Output:
[6, 8, -3]

The row vector combines the matrix rows as 2·row0 + 3·row1, producing [6, 8, -3].

Constraints

• The matrix dimensions are non-negative integers.
• Only non-zero matrix entries count toward nnz.
• right_multiply receives a vector of length cols and returns a vector of length rows.
• left_multiply receives a vector of length rows and returns a vector of length cols.
• Both operations must use time proportional to nnz.
• Invalid vector dimensions must be detected and reported according to the language's normal error mechanism.