Cohesity
Online AssessmentMinimize Maximum Truck Load
Rohit's company produces machines of different weights. The factory produces N machines every day. Each machine is kept in a separate room, and all N rooms are arranged in a line.
k trucks arrive at the factory every day to transport those machines. Each truck can carry one or more machines but will never leave empty.
The workers prefer the truck to be present nearer to the machines it needs to load, so a truck will only carry machines housed in rooms that are next to each other (a contiguous segment).
The truck owner doesn't want his trucks to be overloaded, so he wants the machines distributed among the k trucks such that the maximum weight in a truck is minimized.
The rooms are given as an array a, where a[i] is the weight of the i-th machine. Return the minimum possible value of the maximum weight carried by a single truck.
- ▸a: an array of N integers, the machine weights in room order.
- ▸k: the number of trucks.
- ▸A single integer: the minimized maximum load of any truck.
- 1 ≤ k ≤ N (approximate; the exact bounds were not visible in the OA screenshot)
- 1 ≤ a[i] (approximate)
a = [7, 2, 5, 10, 8] k = 2
18
Split the rooms into [7, 2, 5] and [10, 8].
The loads are 14 and 18, so the maximum load is 18.
No other split into 2 contiguous groups has a smaller maximum.
Binary search on the answer between max(a) and sum(a). For a candidate capacity m, greedily fill trucks left to right, starting a new truck whenever the next machine would exceed m. If at most k trucks are needed, m is feasible, so search lower; otherwise search higher. Same as LeetCode 410 (Split Array Largest Sum).