Fastest parallel test shard
A build team timed every subset of its k test files as a single shard, so shard_time has 2^k entries and shard_time[m] is the measured wall time of the shard holding exactly the files named by mask m, setup included. Entry 0 is the empty shard and takes no time. Instead of running a subset whole, the team can split it into two groups, neither of them empty, that run on separate machines at the same time, and either group can be split again the same way. A split finishes when its slower side finishes, and machines are never scarce. Return one entry per subset, in mask order, holding the earliest that subset can finish. k is at most 12. An empty table returns an empty list.
shard_finish_times(shard_time: list[int]) → list[int][[0,10,12,30]]out[0,10,12,12][[0,5,5,4]]out[0,5,5,4][[0,8,6,20,9,30,24,40]]out[0,8,6,8,9,9,9,9]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[0,10,12,30]][0,10,12,12]not run yetsample[[0,5,5,4]][0,5,5,4]not run yetsample[[0,8,6,20,9,30,24,40]][0,8,6,8,9,9,9,9]not run yetsample