How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Pinterest during technical interviews.

Implement sparse matrix storage, addition, and multiplication

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a way to store a sparse matrix (most entries are zero) and implement efficient operations. You are given matrices using their non-zero entries: - Matrix `A` has shape `(m, n)` and is represented as a list of triples `(row, col, value)` containing only entries where `value != 0`. - Matrix `B` has shape `(n, p)` (for multiplication) and/or shape `(m, n)` (for addition), represented the same way. Implement the following: 1. **Sparse storage**: Choose a representation suitable for efficient operations. 2. **Addition**: Compute `A + B` (only when shapes match), returning the result in the same sparse triple-list form (do not output explicit zeros). 3. **Multiplication**: Compute `A × B`, returning the result in sparse triple-list form. **Constraints** - Dimensions can be large (e.g., up to `1e5` in each direction), but the number of non-zero entries `k` is much smaller than `m*n`. - Input triples may not be sorted. **Output requirements** - Return only non-zero entries. - You may return triples in any order unless otherwise specified.

Quick Answer: This question evaluates understanding of sparse matrix representations, algorithmic efficiency for linear algebra operations, and the ability to manipulate sparse data structures and aggregate non-zero entries.

Part 1: Build CSR Sparse Storage

A sparse matrix has mostly zero values, so storing every cell is wasteful. You are given a matrix of shape m x n as an unsorted list of non-zero triples [row, col, value]. Build a compressed sparse row representation (CSR). If the same cell appears multiple times, add those values together first. If a summed value becomes zero, do not store it. Within each row, columns in the CSR output must be sorted in increasing order.

Constraints

1 <= m, n <= 100000
0 <= len(entries) <= 200000
Input triples may be unsorted
The same coordinate may appear multiple times and must be combined
Values are integers and any final stored value equal to 0 must be omitted

Examples

Input: (3, 4, [[2, 3, 7], [0, 1, 5], [2, 0, 1], [0, 1, -2]])

Expected Output: [[0, 1, 1, 3], [1, 0, 3], [3, 1, 7]]

Explanation: Cell (0, 1) becomes 3 after combining 5 and -2. Row 1 is empty, so row_ptr repeats.

Input: (2, 3, [])

Expected Output: [[0, 0, 0], [], []]

Explanation: An empty sparse matrix still has a valid CSR row pointer array of length m + 1.

Input: (1, 5, [[0, 2, 4], [0, 2, -4], [0, 4, 9]])

Expected Output: [[0, 1], [4], [9]]

Explanation: The two entries at column 2 cancel out, so only column 4 remains.

Input: (4, 4, [[3, 1, 2], [1, 2, 8], [1, 0, 6]])

Expected Output: [[0, 0, 2, 2, 3], [0, 2, 1], [6, 8, 2]]

Explanation: Rows 0 and 2 are empty. Row 1 stores columns 0 and 2 in sorted order.

Hints

A dictionary keyed by (row, col) is a simple way to merge duplicate entries first.
After combining duplicates, group entries by row and sort each row by column before building row_ptr.

Part 2: Add Two Sparse Matrices

You are given two sparse matrices A and B of the same shape m x n. Each matrix is represented as an unsorted list of triples [row, col, value]. A coordinate may appear multiple times inside the same input; its real stored value is the sum of those triples. Compute A + B and return the result as a sparse triple list. Do not include any zero-valued entries. For deterministic grading, sort the output by row first, then by column.

Constraints

1 <= m, n <= 100000
0 <= len(a_entries) + len(b_entries) <= 200000
Both matrices have the same shape m x n
Input triples may be unsorted
Duplicate coordinates may appear and must be combined
Do not return any triple whose final value is 0

Examples

Input: (3, 3, [[0, 1, 2], [1, 1, 5], [2, 0, -1]], [[0, 1, 3], [1, 2, 4], [2, 0, 1]])

Expected Output: [[0, 1, 5], [1, 1, 5], [1, 2, 4]]

Explanation: Cells (0, 1) add to 5, while (2, 0) cancels out to 0 and is omitted.

Input: (2, 2, [], [])

Expected Output: []

Explanation: Adding two empty sparse matrices produces an empty sparse matrix.

Input: (2, 2, [[0, 0, 4], [0, 0, -1], [1, 1, 3]], [[0, 0, -3], [1, 0, 2]])

Expected Output: [[1, 0, 2], [1, 1, 3]]

Explanation: In A, cell (0, 0) becomes 3 after combining duplicates, then cancels with -3 from B.

Input: (1, 1, [[0, 0, 7]], [[0, 0, -7]])

Expected Output: []

Explanation: The only cell sums to zero, so the sparse result is empty.

Hints

Use one hash map keyed by (row, col) and add contributions from both matrices into it.
Only filter out zeros after all additions are complete, because cancellation can happen late.

Part 3: Multiply Two Sparse Matrices

You are given sparse matrix A of shape m x n and sparse matrix B of shape n x p. Each matrix is an unsorted list of triples [row, col, value]. Duplicate coordinates inside the same input should be summed first. Compute the sparse product C = A x B. Return only non-zero entries, sorted by row first and then by column.

Constraints

1 <= m, n, p <= 100000
0 <= len(a_entries) + len(b_entries) <= 200000
Input triples may be unsorted
Duplicate coordinates may appear and must be combined before multiplication
Do not return any triple whose final value is 0
The total number of matching non-zero pair products is small enough to process

Examples

Input: (2, 3, 2, [[0, 0, 1], [0, 2, 2], [1, 1, 3]], [[0, 1, 4], [2, 0, 5], [1, 1, 6]])

Expected Output: [[0, 0, 10], [0, 1, 4], [1, 1, 18]]

Explanation: Row 0 of A combines contributions through k = 0 and k = 2. Row 1 contributes only through k = 1.

Input: (2, 3, 2, [], [[0, 1, 4]])

Expected Output: []

Explanation: If A has no non-zero entries, the product is the zero matrix.

Input: (1, 2, 1, [[0, 0, 2], [0, 1, 3]], [[0, 0, 3], [1, 0, -2]])

Expected Output: []

Explanation: The only output cell is 2*3 + 3*(-2) = 0, so nothing is stored.

Input: (2, 2, 2, [[0, 0, 1], [0, 0, 2], [1, 1, 4]], [[0, 1, 3], [1, 0, 5], [1, 0, -1]])

Expected Output: [[0, 1, 9], [1, 0, 16]]

Explanation: A has a duplicate at (0, 0) that becomes 3. B has duplicates at (1, 0) that become 4.

Hints

Index matrix B by its row, because A[i][k] only interacts with B[k][j].
Accumulate partial products in a hash map keyed by (i, j) so multiple paths through the same inner index can be merged.

Quick Overview

This question evaluates understanding of sparse matrix representations, algorithmic efficiency for linear algebra operations, and the ability to manipulate sparse data structures and aggregate non-zero entries.