Frontend School

GPU Task Scheduler: Memory-Constrained Combinations

DSA
medium

GPU Task Scheduler: Memory-Constrained Combinations

Medium
Backtracking
Arrays
Combinatorics

Overview

Nvidia designs advanced GPUs and systems that power everything from AI research to high-performance computing. Efficient resource allocation is critical in these environments. This problem simulates a scenario where you need to schedule a set of GPU tasks, each with a specific memory footprint, within a finite memory budget. Finding all valid task groupings helps in optimizing system utilization, understanding resource limits, and planning future workloads.

What you need to do / Task

Implement a function findTaskCombinations that, given an array of integers tasks (representing memory requirements) and an integer budget (total available memory), returns all unique combinations of tasks whose total memory requirement does not exceed budget.

  1. Each task can be used at most once in a combination.
  2. The order of tasks within a combination does not matter (e.g., [1, 2] is considered the same as [2, 1]). Your output should sort tasks within each combination in non-decreasing order.
  3. The result should not contain duplicate combinations (e.g., if tasks = [2, 2, 3] and budget = 4, [[2], [2]] is not a valid output; instead, [[2], [2,2], [3]] is expected, where [2] and [2,2] represent combinations formed by distinct task instances). All single tasks that fit within the budget should also be included as valid combinations.

Input & output

  • tasks: An array of integers, where tasks[i] represents the memory requirement (in MB) for the i-th task. All tasks[i] will be positive.
  • budget: An integer, representing the total available memory (in MB). budget will be positive.
  • Return: A number[][] (array of arrays of numbers), where each inner array is a unique combination of task memory requirements that satisfies the conditions. The order of combinations in the outer array does not matter. The order of tasks within each inner array should be non-decreasing.

Clarifications

  • An empty input tasks array should result in an empty number[][] array being returned.
  • If no combinations fit the budget, an empty number[][] array should be returned.
  • The tasks array may contain duplicate memory requirements. These represent distinct tasks that happen to have the same memory footprint.

Examples

1

Example 1

Input:

tasks = [1, 2, 3, 2], budget = 4

Output:

[[1,2], [1,3], [2], [2,2], [3]]

Note:

The tasks are sorted internally to [1, 2, 2, 3].

  • Individual tasks: [1], [2], [3]
  • Combinations: [1,2] (using the first '2'), [1,3], [2,2] (using both '2's). Note: [1,2] using the second '2' is a duplicate of [1,2] using the first '2' and is excluded. Order of combinations and elements within combinations are normalized.
2

Example 2

Input:

tasks = [5, 10, 15], budget = 10

Output:

[[5], [10]]

Note:

Only tasks with memory 5 and 10 fit individually. Any combination including 15, or a combination of 5 and 10, would exceed the budget.

3

Example 3

Input:

tasks = [1, 1, 1, 1], budget = 2

Output:

[[1], [1,1]]

Note:

With multiple tasks of memory 1 and a budget of 2, we can form combinations of [1] (using any single task) and [1,1] (using any two distinct tasks of memory 1). The output ensures uniqueness of combinations.

Constraints

Constraints & assumptions

  • 1 <= tasks.length <= 20
  • 1 <= tasks[i] <= 100
  • 1 <= budget <= 500
  • All tasks[i] and budget are positive integers.
  • The input tasks array may contain duplicate memory requirements.

What interviewers evaluate

  • Correctness: The solution must identify all unique combinations that satisfy the memory budget, and no invalid combinations.
  • Algorithm Design: Effective use of backtracking to explore the solution space while correctly handling duplicates and pruning invalid paths.
  • Time and Space Complexity: Understanding the complexity implications of the chosen approach and optimizing where appropriate (e.g., pruning).
  • Code Quality: Readability, maintainability, and proper use of data structures.

Loading editor...