Problem statement
Design the object model and public API for a sparse matrix that stores only non-zero cells, supporting element access, row / column iteration, and basic arithmetic without ever materializing the dense grid.
Operating context. One process, in-memory. Logical dimensions can be enormous (say a million by a million) while non-zero density is tiny. A storage strategy — dictionary-of-keys, coordinate list, or compressed-sparse-row — is chosen per workload behind one interface. It backs graph adjacency and recommendation-feature matrices where most entries are zero.
Out of scope. Persistence or on-disk formats, distributed / blocked matrices, a dense-matrix fallback path, GPU or BLAS acceleration, and heavy factorizations such as LU or QR — keep to storage, access, transpose, add, and multiply.
What to produce. The class model (a SparseMatrix interface with pluggable storage backends), the public API (get, set, nonZeroCount, transpose, add, multiply, iterate non-zeros), the coordinate-to-storage mapping for the chosen backend, and how setting a cell to zero removes its entry rather than storing a zero — state the storage invariant explicitly.
Must do 5
Functional requirements
- Get and set a cell by row and column, treating any unset cell as zero.
- Store only non-zero cells, dropping a cell from storage when it is set back to zero.
- Iterate the non-zero entries, and iterate a single row or column efficiently.
- Produce the transpose without densifying the matrix.
- Add and multiply two sparse matrices, iterating only over non-zero terms.
Must hold 5
Non-functional requirements
- Memory is O(number of non-zeros), independent of the logical dimensions.