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 Technical Screen rounds at Pinterest.

What role is this question designed for?

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

Implement a Sparse Matrix Class | Pinterest Coding Question

Quick Overview

This question evaluates the ability to design and implement efficient sparse data structures and perform matrix operations, testing knowledge of sparse matrix representation, linear algebra operations (addition and multiplication), and algorithmic complexity analysis.

Implement a Sparse Matrix Class

Company: Pinterest

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a `SparseMatrix` class for matrices that contain mostly zero values. Your class should support the following operations: 1. **Construction and storage** - Initialize a matrix from a dense 2D list of numbers. - Store only non-zero values internally, for example using a dictionary keyed by `(row, column)`. - Keep track of the matrix dimensions. 2. **Printing or conversion** - Provide a method to print the matrix or convert it back into a dense 2D list. 3. **Addition** - Implement matrix addition: `A + B`. - Matrices can be added only if they have the same dimensions. - The result should also be represented as a `SparseMatrix`. 4. **Multiplication** - Implement matrix multiplication: `A * B`. - Matrix multiplication is valid only if `A.columns == B.rows`. - The result should also be represented as a `SparseMatrix`. Discuss the time and space complexity of your implementation, especially in terms of the number of non-zero entries rather than the full matrix size.

Quick Answer: This question evaluates the ability to design and implement efficient sparse data structures and perform matrix operations, testing knowledge of sparse matrix representation, linear algebra operations (addition and multiplication), and algorithmic complexity analysis.

Implement the core behavior of a sparse matrix data structure for matrices that contain mostly zero values. Because the judge calls a function rather than inspecting a class directly, write a function `solution(operation, matrix_a, matrix_b=None)` that internally uses a sparse representation. A sparse matrix should: - Store only non-zero values, such as in a dictionary keyed by `(row, column)`. - Track the number of rows and columns. - Be able to convert itself back to a dense 2D list. - Support matrix addition and matrix multiplication. Your function must support these operations: - `"dense"`: build a sparse matrix from `matrix_a` and return its dense form. - `"add"`: return `matrix_a + matrix_b`. - `"multiply"`: return `matrix_a * matrix_b`. Return the result as a dense 2D list. If the requested operation is invalid or the matrix dimensions are incompatible, return an empty list `[]`. The goal is to use sparse storage internally so that work depends as much as possible on the number of non-zero entries instead of the full matrix size.

Constraints

0 <= number of rows, number of columns <= 200
All input matrices are rectangular
-10^6 <= matrix[i][j] <= 10^6
For addition, both matrices must have the same dimensions
For multiplication, matrix_a columns must equal matrix_b rows

Examples

Input: ("dense", [[0,0,3],[0,0,0],[4,0,5]], None)

Expected Output: [[0,0,3],[0,0,0],[4,0,5]]

Explanation: The sparse structure stores only the three non-zero entries and reconstructs the same dense matrix.

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

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

Explanation: Add corresponding cells. Zeros do not need to be stored internally.

Input: ("add", [[5,0],[0,0]], [[-5,0],[0,0]])

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

Explanation: The only non-zero values cancel out, so the sparse result has no stored entries.

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

Expected Output: [[0,16],[15,0]]

Explanation: Only matching non-zero pairs contribute: row 0 gives 16 in column 1, and row 1 gives 15 in column 0.

Input: ("multiply", [[1,2]], [[1,2]])

Expected Output: []

Explanation: A 1x2 matrix cannot be multiplied by another 1x2 matrix because the inner dimensions do not match.

Input: ("dense", [], None)

Expected Output: []

Explanation: An empty matrix remains empty after sparse conversion and reconstruction.

Hints

A dictionary keyed by `(row, column)` lets you store only non-zero entries and look them up efficiently.
For multiplication, group non-zero values of the second matrix by row so that each non-zero `(i, k)` in the first matrix only combines with useful entries.

Quick Overview