XPeng·Machine Learning Engineer·Technical Phone Screen
- Given an array of dimensions representing a chain of matrices, compute the minimum number of scalar multiplications needed to multiply them all together. Return both the minimum cost and one valid optimal parenthesization.
- Can you reduce the space complexity of your solution, and what are the tradeoffs involved?
- How would your solution change if each multiplication also had a fixed setup cost on top of the scalar multiplication count?
- Compare bottom-up dynamic programming versus top-down memoization for this problem. When would you prefer one over the other?
“I knew the classic DP solution going in but fumbled the parenthesization reconstruction part.”