How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a nan difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Voleon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Voleon during technical interviews.

Implement sparse matrix addition and multiplication

Quick Overview

This question evaluates implementation skills for sparse matrix addition and multiplication, focusing on data structure selection, algorithmic complexity, memory efficiency, and explicit error handling within the Coding & Algorithms domain and the linear algebra/data-structures crossover.

Company: Voleon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: nan

Interview Round: Technical Screen

Implement sparse-matrix operations with explicit error handling. ### Sparse matrix A matrix `A` has dimensions `r x c` and is **sparse**, meaning most entries are zero. You may choose a representation (e.g., hashmap/dictionary keyed by `(row, col)` for non-zero values, or compressed rows), but your implementation should be efficient for sparse inputs. ### Tasks Implement: 1. `add(A, B)` → returns `A + B` 2. `mul(A, B)` → returns `A * B` ### Requirements - If dimensions are incompatible: - For addition: `A` and `B` must have the same shape. - For multiplication: `A` is `r x k`, `B` must be `k x c`. - Incompatible dimensions must trigger clear error handling (e.g., raise an exception or return an error value, as specified by your interface). - Preserve sparsity: avoid iterating over all `r*c` cells. ### Input/Output (one reasonable interface) - Input: two sparse matrices - Output: a sparse matrix (or error) ### Constraints (reasonable interview constraints) - Up to `10^5` non-zero entries per matrix. - Dimensions can be large (e.g., up to `10^9`), so dense storage is not allowed.

Quick Answer: This question evaluates implementation skills for sparse matrix addition and multiplication, focusing on data structure selection, algorithmic complexity, memory efficiency, and explicit error handling within the Coding & Algorithms domain and the linear algebra/data-structures crossover.

Implement two operations on **sparse matrices** (matrices where most entries are zero). A matrix is given as its dimensions `r x c` plus a list of its non-zero entries `[row, col, value]`. Write a single function `solution(op, A, B)` that dispatches on `op`: - `op == "add"` → return `A + B`. The two matrices must have the **same shape** (`rA == rB` and `cA == cB`). If not, return the error sentinel `"ERROR"`. - `op == "mul"` → return `A * B`. If `A` is `r x k` then `B` must be `k x c` (i.e. `cA == rB`). If not, return `"ERROR"`. - Any other `op` value → return `"ERROR"`. **Representation.** Each matrix is `[r, c, entries]` where `entries` is a list of `[row, col, value]` triples for the non-zero cells (in any order). The result must be returned in the same `[r, c, entries]` form, with its `entries` list **sorted ascending by (row, col)** and containing only truly non-zero values (entries whose sum cancels to 0 must be dropped). **Sparsity requirement.** Dimensions can be up to `10^9`, so you must never materialize a dense `r x c` array. Work only with the non-zero entries: build hashmaps keyed by `(row, col)`, and for multiplication index `B`'s non-zeros by their row so each non-zero of `A` only touches the matching row of `B`.

Constraints

Up to 10^5 non-zero entries per matrix.
Dimensions r, c can be up to 10^9, so dense storage is forbidden.
Entries may arrive in any order and may contain duplicate (row, col) pairs that should be summed.
Result entries must be sorted ascending by (row, col) with all zero-valued cells omitted.
Incompatible dimensions (add: differing shape; mul: cA != rB) and any unknown op must return the sentinel 'ERROR'.

Examples

Input: ('add', [2, 2, [[0, 0, 1], [1, 1, 3]]], [2, 2, [[0, 1, 5], [1, 1, 2]]])

Expected Output: [2, 2, [[0, 0, 1], [0, 1, 5], [1, 1, 5]]]

Explanation: Same-shape addition: (1,1) cells 3+2=5, the disjoint (0,0) and (0,1) carry through, sorted by (row, col).

Input: ('add', [2, 2, [[0, 0, 4]]], [2, 2, [[0, 0, -4]]])

Expected Output: [2, 2, []]

Explanation: The only overlapping cell cancels to 0, so it is dropped and the result has no non-zero entries.

Input: ('add', [2, 3, [[0, 0, 1]]], [3, 2, [[0, 0, 1]]])

Expected Output: 'ERROR'

Explanation: Addition requires identical shape; 2x3 vs 3x2 is incompatible, so the error sentinel is returned.

Input: ('mul', [2, 3, [[0, 0, 2], [0, 2, 1], [1, 1, 4]]], [3, 2, [[0, 1, 3], [2, 0, 5], [1, 0, 7]]])

Expected Output: [2, 2, [[0, 0, 5], [0, 1, 6], [1, 0, 28]]]

Explanation: 2x3 times 3x2 -> 2x2. Row 0: 2*B[0]=(_,6) and 1*B[2]=(5,_) give (0,0)=5,(0,1)=6. Row 1: 4*B[1]=(28,_) gives (1,0)=28.

Input: ('mul', [2, 2, [[0, 0, 1]]], [3, 2, [[0, 0, 1]]])

Expected Output: 'ERROR'

Explanation: Multiplication needs cA == rB; here cA=2 but rB=3, so the dimensions don't line up and we return the error sentinel.

Input: ('mul', [1000000000, 1000000000, [[0, 999999999, 2]]], [1000000000, 1000000000, [[999999999, 5, 3]]])

Expected Output: [1000000000, 1000000000, [[0, 5, 6]]]

Explanation: Huge 1e9 dimensions with a single non-zero each: only A[(0, 999999999)] meets B row 999999999, producing (0,5)=2*3=6 without any dense allocation.

Input: ('mul', [2, 2, []], [2, 2, [[0, 0, 9]]])

Expected Output: [2, 2, []]

Explanation: An empty (all-zero) left matrix yields an all-zero product regardless of B.

Input: ('add', [2, 2, []], [2, 2, []])

Expected Output: [2, 2, []]

Explanation: Adding two empty sparse matrices of the same shape yields an empty result.

Input: ('foo', [1, 1, []], [1, 1, []])

Expected Output: 'ERROR'

Explanation: An unrecognized operation falls through to the error sentinel.

Hints

Represent each matrix as a dictionary keyed by (row, col) -> value built only from the non-zero entries. This is the whole trick to preserving sparsity.
For addition, require rA == rB and cA == cB; then merge the two maps, summing overlapping keys and discarding any key whose total is 0.
For multiplication, require cA == rB. Index B's non-zeros by their row (k -> list of (col, value)); then for each non-zero A[(i, k)] = v, only the matching row k of B contributes, so you accumulate v * B[k][j] into result[(i, j)].
Don't forget to drop result entries that cancel to zero, and to sort the final list by (row, col) so the output is deterministic.

Quick Overview