Katkat
Back

Implement sparse matrix storage, addition, and multiplication

PinterestSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a memory-efficient representation for sparse matrices and implement arithmetic operations while leveraging the sparsity of the data.

Sparse Matrix Operations

In many applications, matrices are very large but contain mostly zeros. Storing these as standard 2D arrays is memory-inefficient. Implement a class SparseMatrix that stores only the non-zero elements and supports addition and multiplication.

Requirements

  1. __init__(self, rows, cols): Initialize an empty matrix of size rows x cols.
  2. set(self, r, c, val): Set the value at (r, c) to val.
  3. get(self, r, c): Return the value at (r, c).
  4. add(self, other): Return a new SparseMatrix that is the sum of self and other.
  5. multiply(self, other): Return a new SparseMatrix that is the product of self and other.

Constraints

  • Use a data structure that consumes O(N) space, where N is the number of non-zero elements.
  • Assume rows and cols can be up to 10,000, but N remains manageable (e.g., < 100,000).

Example

# Matrix A: 2x2
# [1, 0]
# [0, 2]
A = SparseMatrix(2, 2)
A.set(0, 0, 1)
A.set(1, 1, 2)

# Addition: A + A
B = A.add(A)
# Result: [[2, 0], [0, 4]]

Hints

Hint 1

Consider using a dictionary or a hash map where the key is the tuple (row, col) and the value is the element to represent non-zero entries.

Hint 2

For addition, iterate through the keys of both matrices and sum values where keys overlap; for multiplication, consider using the Compressed Sparse Row (CSR) format or iterating over columns of the second matrix.

Hint 3

To optimize multiplication, pre-group elements of the second matrix by their row indices to avoid searching for non-zero entries in every iteration.

Follow-up questions

  • How does your implementation change if the matrices are extremely large and stored on disk?
  • What is the time complexity of your multiplication operation in terms of non-zero elements?
  • How would you handle potential memory issues if the matrix is 'dense-sparse' (i.e., the number of non-zero elements approaches rows * cols)?