Analyze matrix multiplication complexity
Company: OpenAI
Role: Machine Learning Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Technical Screen
You are asked in an ML coding interview:
Given two dense matrices A and B, where A has shape (m, n) and B has shape (n, p), you compute C = A @ B (standard matrix multiplication, as in NumPy/PyTorch).
1) What is the time complexity of this operation in Big-O notation (in terms of m, n, p)?
2) What is the space complexity (extra memory usage) of this operation? Clearly state whether you count the output matrix C as part of the space.
Optional follow-up: How does your answer change (if at all) if A and B are batched, e.g., A is (b, m, n) and B is (b, n, p) and you compute a batched matmul?
Quick Answer: This question evaluates understanding of time and space complexity for matrix multiplication and memory accounting in ML workloads, testing competency in asymptotic analysis, linear algebra operations, and resource estimation.