Code RoomFastest parallel test shard
HardPrep Room Coding #4894

Fastest parallel test shard

CodingAlgorithms & data structuresSenior–Staff~30 min

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.

Implement
shard_finish_times(shard_time: list[int]) → list[int]
Examples
in[[0,10,12,30]]out[0,10,12,12]
in[[0,5,5,4]]out[0,5,5,4]
in[[0,8,6,20,9,30,24,40]]out[0,8,6,8,9,9,9,9]
What a strong answer looks like

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:00 of about 30 min
InputExpectedGot
[[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