Implement sparse matrix storage, addition, and multiplication
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design a way to store a sparse matrix (most entries are zero) and implement efficient operations.
You are given matrices using their non-zero entries:
- Matrix `A` has shape `(m, n)` and is represented as a list of triples `(row, col, value)` containing only entries where `value != 0`.
- Matrix `B` has shape `(n, p)` (for multiplication) and/or shape `(m, n)` (for addition), represented the same way.
Implement the following:
1. **Sparse storage**: Choose a representation suitable for efficient operations.
2. **Addition**: Compute `A + B` (only when shapes match), returning the result in the same sparse triple-list form (do not output explicit zeros).
3. **Multiplication**: Compute `A × B`, returning the result in sparse triple-list form.
**Constraints**
- Dimensions can be large (e.g., up to `1e5` in each direction), but the number of non-zero entries `k` is much smaller than `m*n`.
- Input triples may not be sorted.
**Output requirements**
- Return only non-zero entries.
- You may return triples in any order unless otherwise specified.
Quick Answer: This question evaluates understanding of sparse matrix representations, algorithmic efficiency for linear algebra operations, and the ability to manipulate sparse data structures and aggregate non-zero entries.