Add and Multiply Sparse Matrices Given as Row, Column, Value Triples
Company: Pinterest
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A sparse matrix is stored in coordinate form: a list of `[row, col, value]` triples, one for each nonzero cell, where every cell that is not listed is zero. For example, the matrix `[[0, 3, 0], [4, 7, 0], [0, 0, 0]]` is stored as `[[0, 1, 3], [1, 0, 4], [1, 1, 7]]`.
Given two matrices `a` and `b` in coordinate form and an operation `op`, return the sum `a + b` when `op` is `"add"`, or the matrix product `a * b` when `op` is `"multiply"`, in the same coordinate form.
The candidate's report asks for both the sum and the product of two such compressed matrices, with the result in the same compressed form; this version combines them in one function and fixes the input guarantees and the output order in Rules below.
### Function Signature
```python
def sparse_matrix_op(a: list[list[int]], b: list[list[int]], op: str) -> list[list[int]]:
```
### Rules
- Each triple `[r, c, v]` means that the cell in row `r` and column `c` (both zero-based) holds the value `v`.
- Within one input, no `(r, c)` position appears twice and every `v` is nonzero. Triples may appear in any order.
- The matrix shapes are not passed. They are always compatible: for `"add"` the two matrices have the same shape, and for `"multiply"` the number of columns of `a` equals the number of rows of `b`.
- For `"add"`, result cell `(r, c)` is the value of `a` at `(r, c)` plus the value of `b` at `(r, c)`, where a position missing from an input counts as zero.
- For `"multiply"`, result cell `(i, j)` is the sum, over every `k`, of the value of `a` at `(i, k)` times the value of `b` at `(k, j)`.
- Return one `[r, c, v]` triple for each result cell whose value is nonzero. A cell whose contributions cancel to zero is omitted. Sort the triples by row ascending, then by column ascending. Return `[]` when every cell of the result is zero.
### Constraints
- `op` is either `"add"` or `"multiply"`.
- `0 <= len(a), len(b) <= 10^4`
- `0 <= r, c <= 10^9 - 1`; the matrices can be far too large to store densely.
- `-10^4 <= v <= 10^4` and `v != 0` for every input triple.
- For `"multiply"`, the number of pairs made of a triple `[i, k, x]` from `a` and a triple `[k, j, y]` from `b` with the same `k` is at most `10^6`.
- Output values of `"multiply"` can reach `10^14` in absolute value, beyond `2^31 - 1`, so use 64-bit integers. Every output value lies within `±2^53`.
### Examples
**Example 1**
```text
Input: a = [[0, 1, 3], [1, 0, 4], [1, 1, 7]]
b = [[0, 0, 1], [1, 1, -7], [2, 0, 5]]
op = "add"
Output: [[0, 0, 1], [0, 1, 3], [1, 0, 4], [2, 0, 5]]
```
Densely, `a` is `[[0, 3, 0], [4, 7, 0], [0, 0, 0]]` and `b` is `[[1, 0, 0], [0, -7, 0], [5, 0, 0]]`, so the sum is `[[1, 3, 0], [4, 0, 0], [5, 0, 0]]`. Cell `(1, 1)` is `7 + (-7) = 0` and is omitted.
**Example 2**
```text
Input: a = [[0, 1, 3], [1, 0, 4], [1, 1, 7]]
b = [[0, 0, 1], [1, 1, -7], [2, 0, 5]]
op = "multiply"
Output: [[0, 1, -21], [1, 0, 4], [1, 1, -49]]
```
Cell `(0, 1)` is `3 * (-7) = -21`, from `a` at `(0, 1)` and `b` at `(1, 1)`. Cell `(1, 0)` is `4 * 1 = 4`, and cell `(1, 1)` is `7 * (-7) = -49`. The entry of `b` at `(2, 0)` contributes nothing, because column 2 of `a` is empty.
**Example 3**
```text
Input: a = [[0, 1, 3], [0, 0, 2]]
b = [[1, 0, -2], [0, 0, 3]]
op = "multiply"
Output: []
```
Here `a` is the 1 x 2 matrix `[[2, 3]]` and `b` is the 2 x 1 matrix `[[3], [-2]]`. The only result cell is `(0, 0) = 2 * 3 + 3 * (-2) = 0`, so the product has no nonzero cell. The input triples are not sorted.
Overview: Given two sparse matrices stored as lists of row, column and nonzero value triples, return either their sum or their product in the same coordinate form. Tests sparse representations, combining entries by position, dropping cells that cancel to zero, and a canonical row-then-column output order.
Read the full Pinterest Machine Learning Engineer interview experience this question came from
A sparse matrix is stored in coordinate form: a list of `[row, col, value]` triples, one for each nonzero cell, where every cell that is not listed is zero. For example, the matrix `[[0, 3, 0], [4, 7, 0], [0, 0, 0]]` is stored as `[[0, 1, 3], [1, 0, 4], [1, 1, 7]]`.
Given two matrices `a` and `b` in coordinate form and a string `op`, return the sum `a + b` when `op` is `"add"`, or the matrix product `a * b` when `op` is `"multiply"`, in the same coordinate form.
**Rules**
- Each triple `[r, c, v]` means that the cell in row `r` and column `c` (both zero-based) holds the value `v`.
- Within one input, no `(r, c)` position appears twice and every `v` is nonzero. Triples may appear in any order.
- The matrix shapes are not passed. They are always compatible: for `"add"` the two matrices have the same shape, and for `"multiply"` the number of columns of `a` equals the number of rows of `b`.
- For `"add"`, result cell `(r, c)` is the value of `a` at `(r, c)` plus the value of `b` at `(r, c)`, where a position missing from an input counts as zero.
- For `"multiply"`, result cell `(i, j)` is the sum, over every `k`, of the value of `a` at `(i, k)` times the value of `b` at `(k, j)`.
- Return one `[r, c, v]` triple for each result cell whose value is nonzero. A cell whose contributions cancel to zero is omitted. Sort the triples by row ascending, then by column ascending. Return `[]` when every cell of the result is zero.
**Constraints**
- `op` is either `"add"` or `"multiply"`.
- `0 <= len(a), len(b) <= 10^4`
- `0 <= r, c <= 10^9 - 1`; the matrices can be far too large to store densely.
- `-10^4 <= v <= 10^4` and `v != 0` for every input triple.
- For `"multiply"`, the number of pairs made of a triple `[i, k, x]` from `a` and a triple `[k, j, y]` from `b` with the same `k` is at most `10^6`.
- Output values of `"multiply"` can reach `10^14` in absolute value, beyond `2^31 - 1`, so use 64-bit integers (`long` in Java, `long long` in C++). Every output value lies within `±2^53`.
**Example 1**
```text
Input: a = [[0, 1, 3], [1, 0, 4], [1, 1, 7]]
b = [[0, 0, 1], [1, 1, -7], [2, 0, 5]]
op = "add"
Output: [[0, 0, 1], [0, 1, 3], [1, 0, 4], [2, 0, 5]]
```
Densely, `a` is `[[0, 3, 0], [4, 7, 0], [0, 0, 0]]` and `b` is `[[1, 0, 0], [0, -7, 0], [5, 0, 0]]`, so the sum is `[[1, 3, 0], [4, 0, 0], [5, 0, 0]]`. Cell `(1, 1)` is `7 + (-7) = 0` and is omitted.
**Example 2**
```text
Input: a = [[0, 1, 3], [1, 0, 4], [1, 1, 7]]
b = [[0, 0, 1], [1, 1, -7], [2, 0, 5]]
op = "multiply"
Output: [[0, 1, -21], [1, 0, 4], [1, 1, -49]]
```
Cell `(0, 1)` is `3 * (-7) = -21`, from `a` at `(0, 1)` and `b` at `(1, 1)`. Cell `(1, 0)` is `4 * 1 = 4`, and cell `(1, 1)` is `7 * (-7) = -49`. The entry of `b` at `(2, 0)` contributes nothing, because column 2 of `a` is empty.
Constraints
- `op` is either `"add"` or `"multiply"`.
- `0 <= len(a), len(b) <= 10^4`
- `0 <= r, c <= 10^9 - 1`; the matrices can be far too large to store densely.
- `-10^4 <= v <= 10^4` and `v != 0` for every input triple.
- Within one input, no `(r, c)` position appears twice; triples may appear in any order.
- Shapes are not passed and are always compatible: the same shape for `"add"`, and the number of columns of `a` equals the number of rows of `b` for `"multiply"`.
- For `"multiply"`, the number of pairs made of a triple `[i, k, x]` from `a` and a triple `[k, j, y]` from `b` with the same `k` is at most `10^6`.
- Output values of `"multiply"` can reach `10^14` in absolute value, beyond `2^31 - 1`, so use 64-bit integers (`long` in Java, `long long` in C++). Every output value lies within `±2^53`.
Examples
Input: ([[0, 1, 3], [1, 0, 4], [1, 1, 7]], [[0, 0, 1], [1, 1, -7], [2, 0, 5]], 'add')
Expected Output: [[0, 0, 1], [0, 1, 3], [1, 0, 4], [2, 0, 5]]
Explanation: Source Example 1: overlapping cell (1, 1) is 7 + (-7) = 0 and is omitted; cells present in only one input keep their value.
Input: ([[0, 1, 3], [1, 0, 4], [1, 1, 7]], [[0, 0, 1], [1, 1, -7], [2, 0, 5]], 'multiply')
Expected Output: [[0, 1, -21], [1, 0, 4], [1, 1, -49]]
Explanation: Source Example 2: the same inputs as the add case under multiply (op dispatch); b at (2, 0) meets no column 2 of a and contributes nothing.
Hints
- Coordinates go up to 10^9 - 1, so a dense matrix is out of the question: every result value has to be built from the listed triples alone.
- For multiply, ask which triples of b an entry of a at (i, k) can ever be paired with, and which result cells that pairing can touch.
- Several contributions to one cell can cancel to zero; make sure a cell is complete before deciding to drop it, and remember the row-then-column output order.