Variance-Minimizing Split

Reported in interviews at Jump Trading

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.

Related free problems