Quick Overview

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.

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.

Overview: 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

  1. Use a dictionary-of-keys: map row -> {col: val} for fast aggregation and iteration.
  2. Normalize inputs by summing duplicates and dropping zeros before any operation.
  3. For multiplication, iterate rows of A and, for each (i,k), combine with row k of B.
  4. Build the result sparsely and skip zero contributions to avoid dense blow-up.
  5. Sort by (row, col) once at the end to produce a canonical output.

Loading coding console...

Show the approach

Approach

We store each matrix as a dictionary-of-keys mapping row -> {col: value}. During normalization we aggregate duplicates and drop zeros so all operations work on canonical sparse rows. Addition merges the two row dictionaries by key, maintaining sparsity and removing zero sums. Multiplication iterates over nonzeros of a row i in A; for each (i,k) we look up row k in B and accumulate contributions into row i of the result (i.e., C[i,j] += A[i,k] * B[k,j]). Output is converted to a sorted list of triplets for add/multiply or a newline-joined string for printA/printB.

Time complexity:
Add: O(nnz(A) + nnz(B)); Multiply: O(sum over k of nnz_in_col_A[k] * nnz_in_row_B[k])
Space complexity:
O(nnz(A) + nnz(B) + nnz(result))