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
Hints
- Let m[i][j] be the minimal cost to multiply Ai..Aj; try all splits k in [i..j-1].
- Transition: m[i][j] = min_k m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j].
- Store the argmin split to reconstruct a parenthesization.
- Initialize m[i][i] = 0 and build solutions by increasing chain length.
- Top-down memoization yields the same recurrence if you prefer recursion.