FastPrepSparse Matrix Addition and Multiplication
Problems/Sparse Matrix Addition and Multiplication

Sparse Matrix Addition and Multiplication

Pinterest logoPinterest● MediumNEW GRADPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: A PhD new-grad candidate for a machine learning engineer role at Pinterest described four technical rounds over two days. In the first coding round, two sparse matrices were each stored as a list of their nonzero cells, every entry holding a row, a column and a value, and the task was to compute their sum and their product in that same list form. The author solved it with dictionaries and showed one small matrix next to its list form; that matrix is reused in the first two examples here.

The report gives no matrix sizes, limits, function signature, output order, or rule for result cells that add up to zero. Practice choices: both matrices are square with side n up to 10^9, so they cannot be stored in full; one function takes the operation name ADD or MULTIPLY instead of two separate calls; input cells come in any order, with nonzero values from -1000 to 1000 and no repeated position; the result lists only nonzero cells, so cells that cancel to zero are left out; and the result is sorted by row, then by column. The limits and the other examples are ours.

The judged task matches the report at about 80%.

A sparse matrix is mostly zeros, so it is stored in coordinate form: a list of rows [row, col, value], one for each nonzero cell, with zero-based indices. Every cell that is not listed is 0. 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]].

You are given two n x n matrices a and b in coordinate form, with their rows in any order, and a string operation:

  • "ADD": compute a + b, adding the two values of each cell.
  • "MULTIPLY": compute the matrix product a * b. Cell (i, j) of the product is the sum of a[i][k] * b[k][j] over every k.

Return the result in the same coordinate form. List only the nonzero cells of the result: a cell whose contributions add up to 0 is left out. Sort the cells by row, and cells in the same row by column. If the result has no nonzero cell, return an empty list.

n can be as large as 10^9, so the matrices cannot be stored in full.

Function

sparseMatrixOperation(n: int, a: int[][], b: int[][], operation: String) → int[][]

Examples

Example 1

n = 3a = [[0,1,3],[1,0,4],[1,1,7]]b = [[1,1,1],[0,1,-3],[2,2,5]]operation = "ADD"return = [[1,0,4],[1,1,8],[2,2,5]]

Matrix a is [[0,3,0],[4,7,0],[0,0,0]] written as its three nonzero cells. Adding cell by cell: position (0,1) becomes 3 + (-3) = 0, so it is left out; (1,0) stays 4; (1,1) becomes 7 + 1 = 8; (2,2) comes only from b and stays 5. The cells are listed by row, then by column.

Example 2

n = 3a = [[0,1,3],[1,0,4],[1,1,7]]b = [[0,2,1],[1,2,5],[0,0,2]]operation = "MULTIPLY"return = [[0,2,15],[1,0,8],[1,2,39]]

Row 0 of a has only 3 in column 1, so it picks up row 1 of b times 3: cell (0,2) is 3 * 5 = 15. Row 1 of a has 4 in column 0 and 7 in column 1. Cell (1,0) is 4 * 2 = 8, and cell (1,2) is 4 * 1 + 7 * 5 = 39.

Example 3

n = 1000000000a = [[999999999,7,2],[0,1,2],[0,2,1]]b = [[2,4,-6],[1,4,3],[7,0,5]]operation = "MULTIPLY"return = [[999999999,0,10]]

The matrices are 10^9 x 10^9, far too large to store in full. Cell (999999999,0) is 2 * 5 = 10. Cell (0,4) gets 2 * 3 = 6 through index 1 and 1 * (-6) = -6 through index 2. These cancel to 0, so that cell is left out.

Constraints

  • 1 <= n <= 10^9
  • 0 <= a.length, b.length <= 1000
  • a[i].length == b[j].length == 3
  • Each row [row, col, value] has 0 <= row, col < n and a nonzero value with -1000 <= value <= 1000.
  • Within one matrix, no two rows have the same (row, col) position.
  • operation is either "ADD" or "MULTIPLY".

More Pinterest problems

  • Gaussian Naive Bayes Classifier (Machine Learning OA)OA · Seen Nov 2026
  • Top K Pins with Insert and QueryPHONE SCREEN · Seen Nov 2026
  • Pins Violation Log QueriesPHONE SCREEN · Seen Nov 2026
All Pinterest interview questionsSee Pinterest hiring insights
Saved
class Solution {
    public int[][] sparseMatrixOperation(int n, int[][] a, int[][] b, String operation) {
        // Write your code here.
    }
}
Checking account…