Frontend School

Minimize Max GPU Workload

DSA
medium

Minimize Max GPU Workload

Medium
Binary Search
Arrays
Optimization
Greedy

Overview

At Nvidia, optimizing resource utilization is crucial for maximizing throughput in parallel computing. Imagine you have a set of computational tasks, each with a specific complexity (representing the time it takes to complete). You need to distribute these tasks across a limited number of GPUs. The goal is to minimize the maximum workload any single GPU has to handle, ensuring efficient and balanced utilization of your hardware.

This problem challenges you to find the most efficient way to assign tasks to GPUs such that the heaviest loaded GPU has its workload minimized. This is a common optimization pattern in distributed systems and resource scheduling.

What you need to do / Task

Implement the function minimizeMaxWorkload that takes an array of task complexities and the number of available GPUs, and returns the minimum possible value for the maximum workload on any single GPU.

Constraints for task assignment:

  • Tasks must be assigned to GPUs in their original order. That is, if taskComplexities = [t1, t2, t3, t4] and you assign t1 and t2 to GPU1, then t3 must be assigned to GPU2 (or subsequent GPUs), not GPU1. You cannot reorder tasks.
  • Each task must be assigned to exactly one GPU.

Input & output

Function Signature:

function minimizeMaxWorkload(taskComplexities: number[], numGPUs: number): number;

Parameters:

  • taskComplexities: An array of numbers, where taskComplexities[i] represents the complexity (time) of the i-th task.
  • numGPUs: A number representing the total number of GPUs available.

Return Value:

  • A number representing the minimum possible value for the maximum workload on any single GPU across all valid task distributions.

Clarifications

  • If taskComplexities is empty, the maximum workload is 0.
  • Task complexities are always positive integers.
  • numGPUs will always be at least 1.

Examples

1

Example 1

Input:

taskComplexities = [10, 20, 30, 40], numGPUs = 2

Output:

60

Note:

If GPU1 takes tasks [10, 20, 30] (total 60) and GPU2 takes [40] (total 40), the maximum workload is 60. It's not possible to achieve a maximum workload less than 60 with 2 GPUs while maintaining task order. For example, a max workload of 50 would require GPU1 to take [10, 20] (30), then GPU2 would need to take [30, 40] (70), which exceeds 50.

2

Example 2

Input:

taskComplexities = [1, 2, 3, 4, 5], numGPUs = 5

Output:

5

Note:

With 5 GPUs, each task can be assigned to its own GPU. The maximum workload will be the largest single task, which is 5.

3

Example 3

Input:

taskComplexities = [1000000000, 1000000000, 1000000000], numGPUs = 1

Output:

3000000000

Note:

All tasks must be assigned to the single GPU. The total workload will be the sum of all task complexities.

4

Example 4

Input:

taskComplexities = [1, 1, 1, 1, 100], numGPUs = 2

Output:

100

Note:

One optimal distribution is: GPU1 takes [1, 1, 1, 1] (total 4), and GPU2 takes [100] (total 100). The maximum workload is 100.

Constraints

Constraints & assumptions

  • 1 <= taskComplexities.length <= 10^5
  • 1 <= taskComplexities[i] <= 10^9
  • 1 <= numGPUs <= taskComplexities.length
  • The sum of taskComplexities can exceed the standard 32-bit integer limit, so use 64-bit integers or JavaScript's number type which handles large integers up to 2^53 - 1 safely for sums, and 10^9 for individual tasks. The maximum possible sum is 10^5 * 10^9 = 10^{14}, which fits within JavaScript's safe integer range.

What interviewers evaluate

  • Algorithmic Approach: Correct identification and application of an efficient algorithm (e.g., binary search).
  • Correctness: The solution produces the correct minimum maximum workload for all valid inputs, including edge cases.
  • Efficiency: The algorithm runs within acceptable time and space complexity limits for the given constraints.
  • Code Quality: The code is clean, readable, well-structured, and easy to understand.

Loading editor...