Katkat
Back

Implement sparse matrix addition and multiplication

VoleonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates implementation skills for sparse matrix addition and multiplication, focusing on data structure selection, algorithmic complexity, memory efficiency, and explicit error handling within the Coding & Algorithms domain and the linear algebra/data-structures crossover.

Implement sparse-matrix operations with explicit error handling.

Sparse matrix

A matrix A has dimensions r x c and is sparse, meaning most entries are zero.

You may choose a representation (e.g., hashmap/dictionary keyed by (row, col) for non-zero values, or compressed rows), but your implementation should be efficient for sparse inputs.

Tasks

Implement:

  1. add(A, B) → returns A + B
  2. mul(A, B) → returns A * B

Requirements

  • If dimensions are incompatible:
  • For addition: A and B must have the same shape.
  • For multiplication: A is r x k, B must be k x c.
  • Incompatible dimensions must trigger clear error handling (e.g., raise an exception or return an error value, as specified by your interface).
  • Preserve sparsity: avoid iterating over all r*c cells.

Input/Output (one reasonable interface)

  • Input: two sparse matrices
  • Output: a sparse matrix (or error)

Constraints (reasonable interview constraints)

  • Up to 10^5 non-zero entries per matrix.
  • Dimensions can be large (e.g., up to 10^9), so dense storage is not allowed.