Implement a Sparse Matrix Class (store/print/add/multiply)

Problem: Implement a Sparse Matrix Class Implement a SparseMatrix class to store and operate on sparse matrices (most entries are 0). You must support: 1) Storage Store only non-zero entries using a sparse representation. The matrix has m rows and n columns. 2) Printing Implement a print/output method that prints the matrix in a readable dense form: Print m lines, each containing n integers separated by spaces. 3) Addition Implement matrix addition add(other): Only allowed when both matrices have the same shape (m and n). Return a new SparseMatrix as the result. If shapes mismatch, raise an error (or clearly state your chosen behavior). 4) Multiplication Implement matrix multiplication multiply(other): If this matrix is m x n and the other is n x k, the result is m x k. Return a new SparseMatrix. If shapes mismatch, raise an error (or clearly state your chosen behavior). Constraints / Requirements Try to leverage sparsity: prefer iterating only over non-zero entries. Sample I/O (for self-check) Example 1: Addition Matrix A (2x3): 1 0 0 0 0 2 Matrix B (2x3): 0 0 3 0 4 0 A + B: 1 0 3 0 4 2 Example 2: Multiplication Matrix A (2x3): 1 0 0 0 0 2 Matrix C (3x2): 0 5 0 0 7 0 A x C: 0 5 14 0 Scale (discuss in interview) m, n, k up to around 1e3. Number of non-zeros nnz is much smaller than m*n. Explain your data structure choices and time complexity for each operation. Example Input A=2x3: (0,0,1) (1,2,2) B=2x3: (0,2,3) (1,1,4) OP=ADD Output 1 0 3 0 4 2