InterviewDB
Question
Matrix Operations: Implement Efficient Sparse Matrix Addition, Multiplication, and Transpose
Onsite
Question Details
Problem
Implement a SparseMatrix class for large matrices where most entries are zero. Support addition, multiplication, and transpose. Use a compressed representation (e.g., dictionary of non-zero entries or CSR format).
python
class SparseMatrix:
def __init__(self, rows: int, cols: int): ...
def set(self, i: int, j: int, val: float) -> None: ...
def get(self, i: int, j: int) -> float: ...
def add(self, other: 'SparseMatrix') -> 'SparseMatrix': ...
def multiply(self, other: 'SparseMatrix') -> 'SparseMatrix': ...
def transpose(self) -> 'SparseMatrix': ...
Example:
A = SparseMatrix(3,3); A.set(0,0,1); A.set(2,2,3)
B = A.transpose()
B.get(0,0) # -> 1
B.get(2,2) # -> 3
C = A.multiply(B) # should give A * A^T
Follow-ups
- What is the time complexity of your multiply compared to dense matrix multiplication?
- When does sparse representation start saving memory vs. a dense array? Give the crossover formula.
- How would you implement this in CSR (Compressed Sparse Row) format instead of a dict?
- For a 10^6 x 10^6 matrix with 10^8 non-zero entries, what changes in your approach?
Full Details
Problem
Implement a SparseMatrix class for large matrices where most entries are zero. Support addition, multiplication, and transpose. Use a compressed representation (e.g., dictionary of non-zero entries or CSR format).
python
class SparseMatrix:
def __init__(self, rows: int, cols: int): ...
def set(self, i: int, j: int, val: float) -> None: ...
def get(self, i: int, j: int) -> float: ...
def add(self, other: 'SparseMatrix') -> 'SparseMatrix': ...
def multiply(self, other: 'SparseMatrix') -> 'SparseMatrix': ...
def transpose(self) -> 'SparseMatrix': ...
Example:
A = SparseMatrix(3,3); A.set(0,0,1); A.set(2,2,3)
B = A.transpose()
B.get(0,0) # -> 1
B.get(2,2) # -> 3
C = A.multiply(B) # should give A * A^T
Follow-ups
- What is the time complexity of your multiply compared to dense matrix multiplication?
- When does sparse representation start saving memory vs. a dense array? Give the crossover formula.
- How would you implement this in CSR (Compressed Sparse Row) format instead of a dict?
- For a 10^6 x 10^6 matrix with 10^8 non-zero entries, what changes in your approach?
Free preview. Unlock all Voleon Group questions →
About This Question
This is a reported interview question from a voleon group interview during the onsite round.
It covers the following topics: Coding, Arrays, Onsite, Matrix .
More Voleon Group Interview Questions
InterviewDB
Voleon Group SWE Phone - Blanket of White (Matrix/BFS)
InterviewDB
Exchange Broker: Implement an Order Matching Engine for a Simple Exchange
InterviewDB
Voleon Group SWE Phone - Chess Move (Matrix/Simulation)
InterviewDB
Voleon Group SWE Phone - Circular Ring (Arrays/Math)
InterviewDB
Voleon Group SWE Onsite - Good String (Strings)