Implement sparse matrix addition and multiplication
Company: Voleon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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 two operations on **sparse matrices** (matrices where most entries are zero). A matrix is given as its dimensions `r x c` plus a list of its non-zero entries `[row, col, value]`.
Write a single function `solution(op, A, B)` that dispatches on `op`:
- `op == "add"` → return `A + B`. The two matrices must have the **same shape** (`rA == rB` and `cA == cB`). If not, return the error sentinel `"ERROR"`.
- `op == "mul"` → return `A * B`. If `A` is `r x k` then `B` must be `k x c` (i.e. `cA == rB`). If not, return `"ERROR"`.
- Any other `op` value → return `"ERROR"`.
**Representation.** Each matrix is `[r, c, entries]` where `entries` is a list of `[row, col, value]` triples for the non-zero cells (in any order). The result must be returned in the same `[r, c, entries]` form, with its `entries` list **sorted ascending by (row, col)** and containing only truly non-zero values (entries whose sum cancels to 0 must be dropped).
**Sparsity requirement.** Dimensions can be up to `10^9`, so you must never materialize a dense `r x c` array. Work only with the non-zero entries: build hashmaps keyed by `(row, col)`, and for multiplication index `B`'s non-zeros by their row so each non-zero of `A` only touches the matching row of `B`.
Constraints
- Up to 10^5 non-zero entries per matrix.
- Dimensions r, c can be up to 10^9, so dense storage is forbidden.
- Entries may arrive in any order and may contain duplicate (row, col) pairs that should be summed.
- Result entries must be sorted ascending by (row, col) with all zero-valued cells omitted.
- Incompatible dimensions (add: differing shape; mul: cA != rB) and any unknown op must return the sentinel 'ERROR'.
Examples
Input: ('add', [2, 2, [[0, 0, 1], [1, 1, 3]]], [2, 2, [[0, 1, 5], [1, 1, 2]]])
Expected Output: [2, 2, [[0, 0, 1], [0, 1, 5], [1, 1, 5]]]
Explanation: Same-shape addition: (1,1) cells 3+2=5, the disjoint (0,0) and (0,1) carry through, sorted by (row, col).
Input: ('add', [2, 2, [[0, 0, 4]]], [2, 2, [[0, 0, -4]]])
Expected Output: [2, 2, []]
Explanation: The only overlapping cell cancels to 0, so it is dropped and the result has no non-zero entries.
Hints
- Represent each matrix as a dictionary keyed by (row, col) -> value built only from the non-zero entries. This is the whole trick to preserving sparsity.
- For addition, require rA == rB and cA == cB; then merge the two maps, summing overlapping keys and discarding any key whose total is 0.
- For multiplication, require cA == rB. Index B's non-zeros by their row (k -> list of (col, value)); then for each non-zero A[(i, k)] = v, only the matching row k of B contributes, so you accumulate v * B[k][j] into result[(i, j)].
- Don't forget to drop result entries that cancel to zero, and to sort the final list by (row, col) so the output is deterministic.