Sparse Matrix Storage, Addition, and Multiplication
Matrices in Pinterest's recommender pipelines are enormous but almost entirely zeros. Design a SparseMatrix class whose storage is proportional to the number of nonzero entries, supporting:
SparseMatrix.fromDense(rows) // build from a dense array of arrays m.get(r, c) / m.set(r, c, v) a.add(b) // -> new SparseMatrix a.multiply(b) // -> new SparseMatrix m.toDense() m.nnz() // number of stored nonzero entries
Addition and multiplication must exploit sparsity — never iterate the full dense dimensions. Entries that become zero (including by cancellation in add) must be removed from storage: nnz() is how the judge checks you. Dimension mismatches in add or multiply must throw.
Hints
Hint 1
A dict-of-rows representation (row -> { col: value }) gives O(1) get/set and natural sparse iteration; never store zeros — set(r, c, 0) deletes.
Hint 2
For multiply, iterate only A's nonzeros (r, k, va), and for each one only B's row-k nonzeros — cost proportional to matching nonzeros, not dimensions. In add, route every write through set so cancellations delete their entries.