Multiply Two Sparse Integer Matrices Given as Dense Grids
Company: Netflix
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
You are given two integer matrices: `mat1` with `m` rows and `k` columns, and `mat2` with `k` rows and `n` columns. Each matrix is given as a list of rows, and most of their entries are zero.
Return their matrix product: the matrix with `m` rows and `n` columns whose entry in row `i` and column `j` is the sum, over every `t` from `0` to `k - 1`, of `mat1[i][t] * mat2[t][j]`.
### Function Signature
```python
def multiply_sparse(mat1: list[list[int]], mat2: list[list[int]]) -> list[list[int]]:
```
### Rules
- Return a new list of exactly `m` rows, each a list of exactly `n` integers. Rows and entries that are zero are included, not omitted.
- Do not modify `mat1` or `mat2`.
- The inputs are expected to be sparse, but the result must be exact for every input that satisfies the constraints, including dense ones.
### Constraints
- `1 <= m, k, n <= 300`
- `len(mat1) == m` and every row of `mat1` has length `k`.
- `len(mat2) == k` and every row of `mat2` has length `n`.
- `-100 <= mat1[i][t] <= 100` and `-100 <= mat2[t][j] <= 100`
- Every entry of the result has absolute value at most `300 * 100 * 100 = 3000000`, which is well inside the 32-bit signed integer range.
- The result is uniquely determined by the input.
### Examples
**Example 1**
- Input: `mat1 = [[2, 0, 0], [0, 0, -3]]`, `mat2 = [[0, 4], [5, 0], [0, 1]]`
- Output: `[[0, 8], [0, -3]]`
- Explanation: Entry `(0, 1)` is `2 * 4 + 0 * 0 + 0 * 1 = 8`, and entry `(1, 1)` is `0 * 4 + 0 * 0 + (-3) * 1 = -3`. Entries `(0, 0)` and `(1, 0)` are `2 * 0 + 0 * 5 + 0 * 0 = 0` and `0 * 0 + 0 * 5 + (-3) * 0 = 0`.
**Example 2**
- Input: `mat1 = [[0, 0], [0, 0]]`, `mat2 = [[0, 0, 7], [1, 0, 0]]`
- Output: `[[0, 0, 0], [0, 0, 0]]`
- Explanation: The first matrix is all zeros, so the product is the all-zero matrix with 2 rows and 3 columns.
**Example 3**
- Input: `mat1 = [[1, -1, 0, 0]]`, `mat2 = [[2], [2], [0], [9]]`
- Output: `[[0]]`
- Explanation: `1 * 2 + (-1) * 2 + 0 * 0 + 0 * 9 = 0`. Nonzero terms can cancel, and the entry is still reported as `0`.
Overview: Given two integer matrices stored as dense lists of rows in which most entries are zero, return their exact matrix product. It tests handling matrix dimensions correctly and exploiting sparsity to skip work on zero entries while still producing every entry of the result.
Read the full Netflix Machine Learning Engineer interview experience this question came from
You are given two integer matrices: `mat1` with `m` rows and `k` columns, and `mat2` with `k` rows and `n` columns. Each matrix is given as a list of rows, and most of their entries are zero.
Return their matrix product: the matrix with `m` rows and `n` columns whose entry in row `i` and column `j` is the sum, over every `t` from `0` to `k - 1`, of `mat1[i][t] * mat2[t][j]`.
Implement `multiply_sparse(mat1, mat2)`.
### Output format
- Return a new list of exactly `m` rows, in row order `0` to `m - 1`, each a list of exactly `n` integers in column order `0` to `n - 1`.
- Rows and entries that are zero are included, not omitted. An entry whose nonzero terms cancel out is reported as `0`.
- Do not modify `mat1` or `mat2`.
- The inputs are expected to be sparse, but the result must be exact for every input that satisfies the constraints, including dense ones.
- The result is uniquely determined by the input.
### Constraints
- `1 <= m, k, n <= 300`
- `len(mat1) == m` and every row of `mat1` has length `k`.
- `len(mat2) == k` and every row of `mat2` has length `n`.
- `-100 <= mat1[i][t] <= 100` and `-100 <= mat2[t][j] <= 100`
- Every entry of the result, and every partial sum along the way, has absolute value at most `300 * 100 * 100 = 3000000`, which fits in a 32-bit signed integer.
### Example 1
- Input: `mat1 = [[2, 0, 0], [0, 0, -3]]`, `mat2 = [[0, 4], [5, 0], [0, 1]]`
- Output: `[[0, 8], [0, -3]]`
- Explanation: Entry `(0, 1)` is `2 * 4 + 0 * 0 + 0 * 1 = 8`, and entry `(1, 1)` is `0 * 4 + 0 * 0 + (-3) * 1 = -3`. Entries `(0, 0)` and `(1, 0)` are both `0`.
### Example 2
- Input: `mat1 = [[1, -1, 0, 0]]`, `mat2 = [[2], [2], [0], [9]]`
- Output: `[[0]]`
- Explanation: `1 * 2 + (-1) * 2 + 0 * 0 + 0 * 9 = 0`. Nonzero terms can cancel, and the entry is still reported as `0`.
Constraints
- 1 <= m, k, n <= 300
- len(mat1) == m and every row of mat1 has length k
- len(mat2) == k and every row of mat2 has length n
- -100 <= mat1[i][t] <= 100
- -100 <= mat2[t][j] <= 100
- Every result entry (and every partial sum) has absolute value at most 3,000,000, which fits a 32-bit signed integer
Examples
Input: ([[2, 0, 0], [0, 0, -3]], [[0, 4], [5, 0], [0, 1]])
Expected Output: [[0, 8], [0, -3]]
Input: ([[0, 0], [0, 0]], [[0, 0, 7], [1, 0, 0]])
Expected Output: [[0, 0, 0], [0, 0, 0]]
Hints
- Entry (i, j) only changes when both mat1[i][t] and mat2[t][j] are nonzero for some t. How can you skip the terms where either factor is zero?
- Instead of computing each output entry as a dot product, try iterating over the nonzero entries of row i of mat1 and adding a scaled copy of row t of mat2 into output row i.
- Preprocess mat2 once so that each of its rows is a short list of (column, value) pairs for the nonzero entries only.