Matrix Chain Order Interview Questions: Worked DP Answers

Build Matrix Chain Order from the multiplication rule to the recurrence, then trace every split for four matrices and reconstruct the optimal answer.

KnowledgeGate Team

Exam prep & CS education

Updated 1 Nov 20265 min read
Matrix Chain Order Interview Questions: Worked DP Answers

Memorising the cubic recurrence is easy; explaining m[i][j], changing dimensions, and split-table reconstruction is harder. Many candidates can quote the formula but cannot justify it when a follow-up goes deeper. For [40,20,30,10,30], the minimum cost 26000, the optimal parenthesisation ((A1(A2A3))A4), complexity, and follow-ups. The same topic appears in the Dynamic Programming lesson of the DSA course.

What exactly does Matrix Chain Order optimise?

Model answer: Matrix Chain Order, or Matrix Chain Multiplication, finds the least-cost parenthesisation of a fixed compatible sequence. Valid parenthesisations give the same result, but scalar costs can differ. It neither reorders matrices nor calculates entries.

Multiplying p x q by q x r costs p*q*r scalar multiplications and produces p x r. Thus A1(40x20) * A2(20x30) costs 40*20*30 = 24000 and produces 40x30. A2 * A1 is incompatible because 30 != 40, and is forbidden because it changes the order.

For p=[40,20,30,10,30], Ai has shape p[i-1] x p[i]. Thus A1=40x20, A2=20x30, A3=30x10, and A4=10x30. For a refresher on states and transitions, see Dynamic Programming Explained with a Worked 0/1 Knapsack.

Why does parenthesisation matter?

Four matrices have Catalan C3 = 5 full parenthesisations. Their complete costs are:

  • (((A1A2)A3)A4) = 24000 + 12000 + 12000 = 48000

  • ((A1(A2A3))A4) = 6000 + 8000 + 12000 = 26000

  • ((A1A2)(A3A4)) = 24000 + 9000 + 36000 = 69000

  • (A1((A2A3)A4)) = 6000 + 6000 + 24000 = 36000

  • (A1(A2(A3A4))) = 9000 + 18000 + 24000 = 51000

In the winning plan, A2A3 produces 20x10, A1(A2A3) produces 40x10, and multiplying by A4 produces the final 40x30 matrix. The minimum is 26000. The value 14000 covers only the first three matrices in that plan.

Exhaustive search follows Catalan growth, so listing every tree soon becomes impractical. Choosing the currently cheapest adjacent pair is not a general proof of optimality either, because every merge changes the dimensions used by later multiplications.

Diagram comparing five Matrix Chain Order parenthesisations; the highlighted second row is the 26000 minimum and shows intermediate shapes 20x10, 40x10 and 40x30.

How do you derive the DP recurrence?

Let m[i][j] be the minimum scalar multiplications for the fixed subchain Ai...Aj. Set m[i][i]=0 because one matrix needs no multiplication. Let s[i][j] store the best split k, choosing the smallest k to break a tie deterministically.

For a split after Ak, solve Ai...Ak and A(k+1)...Aj. Their results have shapes p[i-1] x p[k] and p[k] x p[j], so the combine cost is p[i-1]*p[k]*p[j]. Therefore:

m[i][j] = min over k=i..j-1 {m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]}

An interval of length L reads shorter intervals, so tabulation fills lengths 2,3,...,n. Memoisation uses the same state and recurrence.

Can you fill the complete cost and split tables?

For length 2:

  • m[1,2]=40*20*30=24000, so s[1,2]=1

  • m[2,3]=20*30*10=6000, so s[2,3]=2

  • m[3,4]=30*10*30=9000, so s[3,4]=3

For length 3, m[1,3] has two candidates. At k=1, the cost is 0+6000+40*20*10=14000. At k=2, it is 24000+0+40*30*10=36000. Store m[1,3]=14000 and s[1,3]=1. For m[2,4], k=2 gives 0+9000+20*30*30=27000, while k=3 gives 6000+0+20*10*30=12000. Store m[2,4]=12000 and s[2,4]=3.

For length 4, the candidates for m[1,4] are 0+12000+40*20*30=36000 at k=1, 24000+9000+40*30*30=69000 at k=2, and 14000+0+40*10*30=26000 at k=3. Hence m[1,4]=26000 and s[1,4]=3.

m

1

2

3

4

1

0

24000

14000

26000

2

-

0

6000

12000

3

-

-

0

9000

4

-

-

-

0

s

1

2

3

4

1

-

1

1

3

2

-

-

2

3

3

-

-

-

3

4

-

-

-

-

Upper-triangular Matrix Chain Order cost and split tables for p=[40,20,30,10,30], with fill lengths and optimal m[1,4]=26000, s[1,4]=3 highlighted.

How do you reconstruct the answer and discuss implementation?

Backtrack through s. First, s[1,4]=3 gives (A1...A3)A4. Then s[1,3]=1 gives A1(A2...A3), and s[2,3]=2 gives A2A3. The final string is ((A1(A2A3))A4). Its costs check out as 6000 + 8000 + 12000 = 26000.

Code
for i = 1 to n:
    m[i][i] = 0
for length = 2 to n:
    for i = 1 to n - length + 1:
        j = i + length - 1
        m[i][j] = infinity
        for k = i to j - 1:
            q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
            if q < m[i][j]:
                m[i][j] = q
                s[i][j] = k
return m[1][n], reconstruct(s, 1, n)

With n matrices, p has n+1 entries. Zero-based implementations must rewrite every index consistently. Use a numeric type wide enough for dimension products and accumulated costs.

What are the time, space and implementation follow-ups?

There are O(n^2) intervals and up to O(n) splits per interval, so time is O(n^3). The two tables use O(n^2) space. Here the algorithm evaluates exactly 3+4+3=10 candidates: three length-2 cells with one split each, two length-3 cells with two each, and one length-4 cell with three.

Memoisation recursively explores and caches the same intervals. Tabulation makes length order explicit and avoids recursion-stack overhead. Both have the same worst-case time and table space when all intervals are needed.

A rolling array does not preserve this interval dependency pattern. Reconstruction also needs stored splits, so do not promise O(n) space while returning the full structure.

Which traps and edge cases should a model answer catch?

Trap

What goes wrong

Repair

Reordering matrices

Solves a different or invalid chain

Preserve A1...An

Counting matrix multiplications

Every plan has n-1, so this cannot distinguish costs

Count scalar multiplications

Forgetting subproblem costs

Chooses only a cheap final merge

Add left, right and combine costs

Wrong dimensions

Uses p[i]*p[k]*p[j]

Use p[i-1]*p[k]*p[j]

Storing cost but no split

Cannot reconstruct parentheses

Maintain s[i][j]

32-bit overflow

A candidate wraps or becomes negative

Use a wide integer and safe infinity

Boundary tests: p=[10,20] means one matrix, cost 0, answer A1. For p=[10,20,30], the cost is 10*20*30=6000, answer (A1A2). For [10,20,30,40], ((A1A2)A3) costs 6000+12000=18000, while (A1(A2A3)) costs 24000+8000=32000.

Dimensions must be positive and p needs at least two entries. Consecutive entries ensure compatibility.

How should you answer this topic in an interview?

Foundation prompts test the two-matrix rule or compare parenthesisations. Derivation prompts cover state, recurrence, and fill order. Dry runs ask for one cell; follow-ups cover reconstruction, complexity, overflow, memoisation, and edge cases. DSA Interview Questions: 7 Patterns for Placements gives a broader structure.

The 45-second answer: m[i][j] is the cheapest cost for Ai...Aj. Try every k, add both subproblem costs and p[i-1]*p[k]*p[j], fill shorter intervals first, and save k to reconstruct. The result is O(n^3) time and O(n^2) space. Checksum: p=[40,20,30,10,30] -> 26000 -> ((A1(A2A3))A4).

Continue with DSA using Java for implementation practice, or Coding for Placements for broader coding-round preparation.