Design Data Structure for Sparse Matrices Operations
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
Analytics engine stores extremely sparse numeric matrices.
##### Question
Design a data structure to store two sparse matrices and implement print(), add(A,B) and multiply(A,B). Discuss complexity for each operation.
##### Hints
Use dictionary-of-keys or CSR; pre-index rows and columns to speed multiplication.
Quick Answer: This question evaluates a candidate's ability to design efficient data structures and implement algorithms for sparse matrix storage and operations, emphasizing space-efficient representations, matrix arithmetic, and computational complexity reasoning.
You are given two sparse integer matrices A and B. Each matrix is specified by its dimensions and a list of nonzero entries as [row, col, val] with 0-based indices. Multiple entries for the same (row, col) may appear and must be summed; any resulting zero is removed. Implement a function that stores both matrices in a dictionary-of-keys structure and supports: (1) add: return the canonical sparse triplet list of A + B (only if dimensions match), (2) multiply: return the canonical sparse triplet list of A × B (only if A.cols == B.rows), and (3) printA / printB: return a newline-separated string of canonical triplets "i j v" for A or B. Canonical triplet order is sorted by row, then column ascending.
Constraints
- 1 <= dimA[0], dimA[1], dimB[0], dimB[1] <= 100000
- 0 <= len(A_entries) + len(B_entries) <= 200000
- Entries use 0-based indices: 0 <= i < rows, 0 <= j < cols
- Values are 32-bit signed integers; duplicates at the same (i,j) are summed; zeros are omitted
- For op == 'add': dimA == dimB
- For op == 'multiply': dimA[1] == dimB[0]
- Output for add/multiply: list of [i,j,val] sorted by i, then j
- Output for printA/printB: newline-separated 'i j v' lines in sorted order
- Do not mutate inputs; raise ValueError on invalid indices or incompatible dimensions
Hints
- Use a dictionary-of-keys: map row -> {col: val} for fast aggregation and iteration.
- Normalize inputs by summing duplicates and dropping zeros before any operation.
- For multiplication, iterate rows of A and, for each (i,k), combine with row k of B.
- Build the result sparsely and skip zero contributions to avoid dense blow-up.
- Sort by (row, col) once at the end to produce a canonical output.