Implement sparse matrix addition and multiplication
Problem Description
Implement sparse matrix addition and multiplication, ensuring efficient operations and explicit error handling.
Sparse Matrix Definition
A matrix A with dimensions r x c is considered sparse if most of its entries are zero. Candidates should choose a suitable representation (e.g., a hashmap/dictionary keyed by (row, col) for non-zero values, or compressed row/column storage) that ensures efficiency for sparse inputs.
Required Operations
Implement the following functions:
add(A, B): Returns the sum of matricesAandB(A + B).mul(A, B): Returns the product of matricesAandB(A * B).
Requirements
- Dimension Compatibility Error Handling:
- For addition (
A + B): MatricesAandBmust have identical dimensions. - For multiplication (
A * B): IfAis anr x kmatrix, thenBmust be ak x cmatrix. - Any dimension incompatibility must result in clear error handling (e.g., raising an exception or returning an error value, as defined by the chosen interface).
- For addition (
- Sparsity Preservation: The implementation must be efficient for sparse inputs, specifically avoiding iteration over all
r*ccells.
Input/Output Interface
- Input: Two sparse matrices.
- Output: A sparse matrix representing the result, or an error if dimensions are incompatible.
Constraints
- Each input matrix can have up to
10^5non-zero entries. - Matrix dimensions (
r,c,k) can be very large, up to10^9. This implies that dense storage for matrices is not permissible.
AI interview prep
Core dilemma
Managing extremely large potential matrix dimensions (up to 10^9) with a relatively small number of non-zero elements (up to 10^5), requiring algorithms and data structures that scale with the number of non-zero elements (NNZ) rather than the full matrix dimensions, thereby avoiding O(R*C) operations.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Implement sparse matrix addition and multiplication
Problem Description
Implement sparse matrix addition and multiplication, ensuring efficient operations and explicit error handling.
Sparse Matrix Definition
A matrix A with dimensions r x c is considered sparse if most of its entries are zero. Candidates should choose a suitable representation (e.g., a hashmap/dictionary keyed by (row, col) for non-zero values, or compressed row/column storage) that ensures efficiency for sparse inputs.
Required Operations
Implement the following functions:
add(A, B): Returns the sum of matricesAandB(A + B).mul(A, B): Returns the product of matricesAandB(A * B).
Requirements
- Dimension Compatibility Error Handling:
- For addition (
A + B): MatricesAandBmust have identical dimensions. - For multiplication (
A * B): IfAis anr x kmatrix, thenBmust be ak x cmatrix. - Any dimension incompatibility must result in clear error handling (e.g., raising an exception or returning an error value, as defined by the chosen interface).
- For addition (
- Sparsity Preservation: The implementation must be efficient for sparse inputs, specifically avoiding iteration over all
r*ccells.
Input/Output Interface
- Input: Two sparse matrices.
- Output: A sparse matrix representing the result, or an error if dimensions are incompatible.
Constraints
- Each input matrix can have up to
10^5non-zero entries. - Matrix dimensions (
r,c,k) can be very large, up to10^9. This implies that dense storage for matrices is not permissible.