Quick Overview

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.

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.

Overview: 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

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

Loading coding console...

Show the approach

Approach

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.

Time complexity:
O(n^3)
Space complexity:
O(n^2)