PPractick

The problem

A video platform splits a long upload into k consecutive segments to encode on k machines in parallel. The job finishes when the slowest machine finishes, so the goal is to split the array of chunk sizes into k contiguous, non-empty parts that minimise the largest part's sum. It's the same problem as book allocation under a different name. Binary search on the answer (the largest allowed part sum) between the biggest single chunk and the total, with a greedy count of how many parts that limit forces.

Example: nums = [7, 2, 5, 10, 8], k = 2 → 18 ([7, 2, 5] and [10, 8]).

Function signature

int splitArray(const vector<int>& nums, int k);  // 1 <= k <= nums.size()

Test cases

Input (nums, k)	Output	Explanation
([7, 2, 5, 10, 8], 2)	18	[7, 2, 5] and [10, 8]
([1, 2, 3, 4, 5], 2)	9	[1, 2, 3] and [4, 5]
([1, 4, 4], 3)	4	One element per part
([10], 1)	10
([2, 3, 1, 2, 4, 3], 5)	4	For example [2], [3], [1, 2], [4], [3]

(Confirm: the parts are contiguous and non-empty; k ≤ n.)

How interviewers phrase it

• "Split an array into k subarrays to minimise the largest subarray sum" (LeetCode 410, Hard).
• Known variously as book allocation, painter's partition, or ship-capacity-in-D-days.
• Sometimes solved with DP, which is O(k·n²); the binary search is much faster.

Clarifying questions to ask

1. Must the parts be contiguous and non-empty?
2. Can values be zero or negative? (With negatives, the greedy check fails; values here are non-negative.)
3. How large can the sums get?

Follow-ups to expect

1. "What's the DP solution?"
2. "Why is binary search faster?"
3. "Why must values be non-negative for the greedy check?"
4. "How is this related to book allocation?"
5. "Complexity?"

Related questions

• Book Allocation Problem Hard
• Minimize Max Distance to Gas Station Hard
• Koko eating bananas Medium
• Minimum days to make M bouquets Medium
• Find the smallest divisor Medium
• Capacity to Ship Packages Within D Days Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in