Quick 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.

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

  1. 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.
  2. 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.
  3. 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.

Loading coding console...

Show the approach

Approach

Add: concatenate the triples of both inputs, sort them by (row, column), and sweep runs of equal positions, summing each run. A position listed in only one input forms a run of one, which is exactly the rule that a missing position counts as zero; a run whose sum is zero is dropped. Because the sweep visits positions in sorted order, the output is already ordered by row and then column.

Multiply: group the triples of b by their row k. A triple [i, k, x] of a can only contribute to result cells in row i, and only through the triples [k, j, y] in row k of b, each adding x * y to cell (i, j); triples of a whose column k is not a row of b contribute nothing and are skipped. Group the remaining triples of a by row i, process the rows in ascending order, and for each row accumulate contributions in a map keyed by column j. Every term a(i, k) * b(k, j) with both factors nonzero is added exactly once, and terms with a zero factor are zero anyway, so each accumulated value equals the definition of the product cell. Emit the row's columns in ascending order, skipping columns whose total cancelled to zero.

Edge cases: either input empty (add returns the other input sorted, multiply returns []); full cancellation (the cell is omitted and the result can be []); coordinates up to 10^9 - 1 (never allocate a dense matrix); and sums beyond 2^31 - 1 (each product is at most 10^8 in absolute value, so accumulate in 64-bit integers: long in Java, long long in C++).

Time complexity:
O((|a| + |b|) log(|a| + |b|) + P log P), where P <= 10^6 is the number of (a, b) triple pairs that share an inner index (multiply only)
Space complexity:
O(|a| + |b| + R), where R is the number of nonzero result cells