Katkat
Back

Find Minimum Processing Rate

AppleMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use binary search on a search space to find an optimal minimum processing rate that satisfies a global deadline constraint.

Problem Statement

You are managing a cluster that needs to process a sequence of n tasks, given as an array of integers tasks, where tasks[i] represents the number of units in the i-th task. You have a fixed amount of time h hours to finish all tasks.

Each hour, you can choose one task and process up to k units of that task. If a task has fewer than k units remaining, you spend the entire hour finishing that task and cannot move to another task until the next hour. You want to find the smallest integer k (the processing rate) such that you can complete all tasks within h hours.

Implement the function: def minProcessingRate(tasks: List[int], h: int) -> int:

Constraints

  • 1 <= tasks.length <= 10^4
  • 1 <= tasks[i] <= 10^9
  • tasks.length <= h <= 10^9

Examples

Example 1: Input: tasks = [3, 6, 7, 11], h = 8 Output: 4 Explanation: With rate 4, the tasks take: ceil(3/4)=1, ceil(6/4)=2, ceil(7/4)=2, ceil(11/4)=3. Total hours = 1+2+2+3 = 8.

Example 2: Input: tasks = [30, 11, 23, 4, 20], h = 5 Output: 30 Explanation: You must process each task in one hour to finish within 5 hours.

Edge Cases

  • If h is equal to the number of tasks, the rate k must be at least the maximum value in tasks.
  • If h is very large, the minimum rate k will be 1.

Hints

Hint 1

Notice that if a rate `k` works, any rate greater than `k` will also work, suggesting the function is monotonic.

Hint 2

The search space for the rate `k` ranges from 1 to the maximum value in the `tasks` array.

Hint 3

For a given `k`, the number of hours required for a task of size `s` is calculated as `(s + k - 1) // k` using integer division.

Follow-up questions

  • What is the time complexity of your solution in terms of N and the maximum task value M?
  • How would your approach change if you were allowed to process multiple tasks in a single hour, but the total units processed per hour could not exceed `k`?
  • What would be the impact on performance if `h` is significantly smaller than the number of tasks?