Variance-Minimizing Split
Problem statement
Given an array of numbers a, partition it into k contiguous groups (using $k-1$ split points) to minimize the total size-weighted variance $\sum_g \text{len}_g \cdot \mathrm{Var}_g$, which equals the total sum of squared deviations across the groups.
Implement:
def min_weighted_variance(a, k):
...
It takes the list a and the number of groups k, and returns the minimum achievable total size-weighted variance as a float. When $k \ge \text{len}(a)$ every element can be its own group, so the answer is 0.0.
Example
min_weighted_variance([1, 2, 10, 11], 2) -> 1.0: the best split is [1,2] | [10,11], each group contributing SSD $0.5$, for a total of $1.0$ (any other split is worse).
Show hint
Can the cost of any contiguous group be expressed through running totals so it is cheap to evaluate for arbitrary endpoints?
Relevant roles: ML Engineer, Applied Scientist, Data Scientist and Forward Deployed Engineer.