←ENG-DSA-016AWS Lambda Job Packing (DP / Knapsack)
00:00
🐍 Python Idle
Mode:Web

AWS Lambda Job Packing (DP / Knapsack)

CompaniesAWS, Vercel
Est. Time~45 min
LevelSenior
Dynamic Programming0/1 Knapsack
🚨 P0 Incident
AWSVercel

AWS Lambda charges by RAM-seconds. Vercel's background job system packs multiple customer jobs into a single Lambda invocation to minimize cost. Given a list of jobs each with a RAM requirement and a priority score, find the optimal combination that maximizes priority without exceeding the Lambda's RAM limit. This is NP-hard in general but solvable in pseudo-polynomial time with DP.

📥 Assigned to:You — Senior Engineer
Your Task

We rent AWS Lambda instances with a maximum RAM capacity of M MB. We have a queue of background jobs, each requiring a specific amount of RAM and yielding a specific priority score. Pick the optimal subset of jobs to run on a single Lambda to maximize the priority score without exceeding M.

⏱ Time: O(n * M)💾 Space: O(n * M)
Example 1
Input:  costs=[10, 20, 30], priorities=[60, 100, 120], max_ram=50
Output: 220 (Jobs 2 and 3)
Example 2
Input:  costs=[100], priorities=[500], max_ram=50
Output: 0
🔒 +3 hidden test cases — revealed on Submit
Hints
Loading editor…
Test Output
▶ Run Code to test against examples · Submit to judge all 5 test cases
EngPrep — Real Engineering. Real Interviews.