Compute optimal matrix multiplication order
Company: XPeng
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an array dims[0..n] where matrix i has dimensions dims[i-1] × dims[i] (for i = 1..n), compute the minimum number of scalar multiplications needed to multiply the chain M1…Mn. Return both the minimal cost and one optimal parenthesization. Analyze time and space complexity. Follow-ups: reduce space to O(n^
2); handle an extra fixed setup cost per multiplication; compare bottom-up DP vs. top-down memoization.
Quick Answer: This question evaluates a candidate's understanding of dynamic programming, optimal substructure, and algorithmic optimization for matrix chain multiplication, including reconstructing an optimal parenthesization and adapting to variant cost models.
Given an integer array dims of length n+1 (n >= 1), where matrix Ai has dimensions dims[i-1] x dims[i] for i = 1..n, compute the minimum number of scalar multiplications needed to multiply the chain A1...An. Return both the minimal cost and one optimal fully parenthesized order as a string built from 'A1'..'An' with parentheses and no spaces. If n = 1, return cost 0 and 'A1'. If multiple optimal orders exist, return any one of them.
Constraints
- 2 <= len(dims) <= 200
- 1 <= dims[i] <= 10^4
- The number of matrices is n = len(dims) - 1
- Return a fully parenthesized string; matrices are named A1..An
Solution
from typing import List, Dict, Any
def matrix_chain_order(dims: List[int]) -> Dict[str, Any]:
n = len(dims) - 1
if n < 1:
raise ValueError("dims must have length >= 2 (at least one matrix)")
# m[i][j]: minimal cost for Ai..Aj; 1-indexed for convenience
m = [[0] * (n + 1) for _ in range(n + 1)]
# s[i][j]: split point that attains minimal cost for Ai..Aj
s = [[0] * (n + 1) for _ in range(n + 1)]
for L in range(2, n + 1): # chain length
for i in range(1, n - L + 2):
j = i + L - 1
best = float('inf')
best_k = i
for k in range(i, j):
cost = m[i][k] + m[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
if cost < best:
best = cost
best_k = k
m[i][j] = best
s[i][j] = best_k
def build(i: int, j: int) -> str:
if i == j:
return f"A{i}"
k = s[i][j]
return f"({build(i, k)}{build(k + 1, j)})"
order = build(1, n)
return {"cost": m[1][n], "order": order}
Explanation
Use bottom-up dynamic programming. m[i][j] stores the minimal scalar multiplications to compute the product Ai..Aj. For each chain length L and start i, try all split positions k between i and j and choose the one minimizing m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j]. Store the argmin in s to reconstruct a fully parenthesized order via recursion. Base case m[i][i] = 0 yields cost 0 for a single matrix. The result is m[1][n] and the reconstructed order.