PPractick

The problem

You're optimizing a deep learning inference pipeline at an AI infra company. A forward pass requires multiplying a chain of weight matrices together: M1 × M2 × M3 × ... × Mn. Matrix multiplication is associative — the final result is the same regardless of how you parenthesize the multiplications — but the computational cost (number of scalar multiplications) varies wildly depending on the order you multiply them in. Your job: given the dimensions of each matrix in the chain, find the minimum number of scalar multiplications needed to compute the full product, using a bottom-up (iterative, not recursive) DP approach — this matters because the inference engine runs this optimization at startup on every model load, and recursion with memoization adds overhead and stack-depth risk for long chains.

Matrices are given via an array arr of dimensions, where matrix i (1-indexed from 1 to n-1) has dimensions arr[i-1] x arr[i]. So for n matrices, arr has n+1 elements.

Function signature

int matrixChainOrder(vector<int>& arr);

Test cases

Input arr	Output	Explanation
[40,20,30,10,30]	26000	4 matrices: 40×20, 20×30, 30×10, 10×30 — optimal parenthesization gives 26000 multiplications
[10,20,30]	6000	2 matrices: 10×20, 20×30 — only one way to multiply → 102030 = 6000
[10,20,30,40,30]	30000	4 matrices — optimal order yields 30000
[5,10]	0	Single matrix, no multiplication needed
[1,2,3,4,5,6]	58	5 matrices, classic small textbook example

(Constraints typically: 1 <= arr.length <= 100, 1 <= arr[i] <= 500. Note: arr.length == n+1 for n matrices.)

How interviewers phrase it

• "Given dimensions of a chain of matrices, find the minimum number of scalar multiplications needed to multiply them all together, in any valid parenthesization order."
• This is the textbook Matrix Chain Multiplication (MCM) problem — often explicitly named by the interviewer since it's a classic CLRS/GeeksforGeeks staple, frequently used as the canonical teaching example for "interval DP."
• A bottom-up-specific ask is a strong signal they want to see you avoid recursion entirely and reason about fill order of a DP table directly — testing whether you understand the dependency structure, not just whether you can write memoized recursion.

Clarifying questions to ask

1. Is arr guaranteed to represent a valid chain (i.e., arr.length == n+1 for n matrices, with consecutive dimensions compatible for multiplication)? (Yes by construction, since arr[i-1] x arr[i] defines matrix i.)
2. Do you want just the minimum cost (scalar multiplication count), or also the actual optimal parenthesization (bracket placement)?
3. Should I implement this strictly bottom-up (iterative table-filling), or is top-down memoization acceptable as a starting point before converting? (Confirm explicitly — bottom-up is the asked-for deliverable here.)
4. What's the maximum chain length? (Up to ~100 matrices means O(n³) ≈ 1M operations, very feasible — confirms the standard O(n³) DP is the expected solution, not something more exotic.)

Follow-ups to expect

1. "Can you reconstruct the optimal parenthesization (bracket string), not just the cost?"
2. "Why is this O(n³) and not something faster?"
3. "How does this relate to Burst Balloons / Minimum Cost to Cut a Stick / Palindrome Partitioning II?"
4. "Can you convert your bottom-up solution back to top-down with memoization, and which is better here?"
5. "What's the space complexity, and can you reduce it?"
6. "What if some matrix multiplications are forbidden/restricted (e.g., a custom adjacency constraint)?"

Related questions

• Matrix chain multiplication Hard
• Minimum cost to cut the stick Hard
• Burst balloons Hard
• Palindrome partitioning II Hard
• Different Ways to Evaluate a Boolean Expression Medium
• Partition Array for Maximum Sum Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in