How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Maximize Value Under a Budget | Amazon Coding Question

Maximize Value Under a Budget

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an array of items. Each item has a price and a value, and you are given a total budget. Each item can be purchased at most once. Implement a function that returns the maximum total value you can obtain without spending more than the budget. Follow-ups: 1. How would the solution change if you must spend exactly the entire budget? 2. How would the solution change if each item has a limited available quantity instead of being available at most once? Discuss the algorithm and time/space complexity.

Quick Answer: This question evaluates combinatorial optimization and algorithm design skills for resource-constrained selection problems, focusing on concepts exemplified by the 0/1 knapsack and its variants.

Part 1: Maximize Total Value Without Exceeding the Budget

You are given a list of items where each item is [price, value]. You have a total budget, and each item can be purchased at most once. Return the maximum total value you can obtain without spending more than the budget. If no item can be purchased, return 0.

Constraints

0 <= len(items) <= 200
0 <= budget <= 10000
1 <= price <= 1000
0 <= value <= 1000

Examples

Input: ([[2, 3], [3, 4], [4, 5], [5, 8]], 5)

Expected Output: 8

Explanation: Buying only the item with price 5 gives value 8, which is better than buying the items with prices 2 and 3 for total value 7.

Input: ([[1, 2], [2, 4], [3, 4], [2, 5]], 5)

Expected Output: 11

Explanation: Choose items with prices 1, 2, and 2 for total cost 5 and total value 2 + 4 + 5 = 11.

Input: ([], 10)

Expected Output: 0

Explanation: There are no items to buy.

Input: ([[7, 100]], 0)

Expected Output: 0

Explanation: A zero budget means nothing can be purchased.

Input: ([[6, 9]], 6)

Expected Output: 9

Explanation: The single item fits exactly within the budget.

Hints

Let dp[b] represent the best value you can achieve with budget b.
Iterate budgets from high to low for each item so that each item is used at most once.

Part 2: Maximize Total Value While Spending Exactly the Budget

You are given a list of items where each item is [price, value]. You have a total budget, and each item can be purchased at most once. This time, you must spend exactly the entire budget. Return the maximum total value among all ways to spend exactly the budget. If it is impossible to spend exactly the budget, return -1.

Constraints

0 <= len(items) <= 200
0 <= budget <= 10000
1 <= price <= 1000
0 <= value <= 1000

Examples

Input: ([[2, 3], [3, 4], [4, 5], [5, 8]], 5)

Expected Output: 8

Explanation: Two exact combinations exist: price 5 alone gives value 8, and prices 2 + 3 give value 7. The maximum is 8.

Input: ([[4, 10], [5, 11]], 3)

Expected Output: -1

Explanation: No subset of items has total price exactly 3.

Input: ([[1, 2], [2, 4], [3, 4], [2, 5]], 5)

Expected Output: 11

Explanation: The best exact combination is prices 1 + 2 + 2 for total value 11.

Input: ([], 0)

Expected Output: 0

Explanation: Choosing no items spends exactly 0 and yields value 0.

Input: ([], 5)

Expected Output: -1

Explanation: With no items, it is impossible to spend exactly 5.

Hints

Unlike the usual knapsack setup, unreachable states should not start at 0. Use a sentinel value to mark impossible sums.
You still need to iterate the budget backward for each item because every item can be chosen at most once.

Part 3: Maximize Total Value With Limited Quantities

You are given a list of item types where each item is [price, value, quantity]. You have a total budget. For each item type, you may buy at most quantity copies. Return the maximum total value you can obtain without spending more than the budget.

Constraints

0 <= len(items) <= 200
0 <= budget <= 10000
1 <= price <= 1000
0 <= value <= 1000
0 <= quantity <= 10^9

Examples

Input: ([[2, 3, 3], [3, 4, 2], [4, 5, 1]], 10)

Expected Output: 14

Explanation: One optimal choice is two copies of the 2-price item and two copies of the 3-price item: total cost 10, total value 14.

Input: ([[5, 10, 1], [3, 7, 3]], 9)

Expected Output: 21

Explanation: Buying three copies of the 3-price item uses the full budget and gives value 21.

Input: ([[2, 5, 0], [3, 6, 0]], 10)

Expected Output: 0

Explanation: All quantities are zero, so nothing can be purchased.

Input: ([[1, 1, 100], [4, 10, 1]], 4)

Expected Output: 10

Explanation: Although the 1-price item has many copies, buying the single 4-price item gives a higher value.

Input: ([[2, 3, 5]], 0)

Expected Output: 0

Explanation: A zero budget means the answer is always 0.

Hints

A naive loop that tries every copy one by one can be too slow when quantities are large.
Try splitting each quantity into groups of sizes 1, 2, 4, ... so the problem turns into a 0/1 knapsack over grouped bundles.

Quick Overview

This question evaluates combinatorial optimization and algorithm design skills for resource-constrained selection problems, focusing on concepts exemplified by the 0/1 knapsack and its variants.