Optimize GPU Jobs with Knapsack | Dataford Interview Questions

RAMP Consulting Group runs parallel GPU training jobs, where each job can use one of several GPU configurations. Choose at most one configuration for each job so the total GPU allocation does not exceed the available budget and the total training value is maximized.

Return both the maximum total value and one optimal configuration for every job. Represent a selected configuration by its zero-based option index, or use -1 if the job is not scheduled. If multiple allocations have the same value, return any one of them.

Formal Specification

Implement max_training_value(jobs, gpu_budget), where jobs is a list of jobs and each job is a list of (gpu_count, value) pairs. gpu_count and value are non-negative integers. Return a dictionary with value, the maximum total value, and allocation, a list of option indices with one entry per job.

Constraints

0 <= len(jobs) <= 1,000
0 <= len(jobs[i]) <= 20
1 <= gpu_count <= gpu_budget <= 10,000
0 <= value <= 10^9
Each job may contribute at most one configuration

Function Signature

def max_training_value(jobs, gpu_budget):

Your question is Optimize GPU Jobs with Knapsack. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

0 <= len(jobs) <= 1,000
0 <= len(jobs[i]) <= 20
1 <= gpu_count <= gpu_budget <= 10,000
0 <= value <= 10^9
Each job may contribute at most one configuration

Function Signature

def max_training_value(jobs, gpu_budget):

Your question is Optimize GPU Jobs with Knapsack. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.