Stack Bash - Master data structures and algorithms


Let's say you sell jewelry. Each item in your store has a specific weight and value.
You are asked to sell a bag that can hold a specific amount of weight.
Write a function that returns the maximum total value that the bag can hold.
For example, let's say you have a bag with a capacity of 50 oz, with the following items in stock:
0Ring15 oz$2
1Necklace30 oz$7
2Bracelet25 oz$3
3Earrings20 oz$12
These items are passed into your function as two array inputs, along with the bag capacity. Each item is represented by the same index in both arrays.
Note that you can only pick either 0 or 1 of each item, not a fraction of one nor a multiple.


jewelry_values = [2, 7, 3, 12]
jewelry_weights = [15, 30, 25, 20]
capacity = 50
output = knapsack(jewelry_values, jewelry_weights, capacity)
print(output) # 19
Your function should return 19, the sum of the value of a Necklace ($7) and earrings ($2) (Item 1 and Item 3), which fit in a 50 oz bag.


8 Essential Recursion & Dynamic Programming Coding Interview Problems

Master Recursion & Dynamic Programming by trying the coding challenges below.
  1. 1.FibonacciEasy
  2. 2.Unique pathsMedium
  3. 3.KnapsackMedium
  4. 4.Subset sumMedium
  5. 5.Power setMedium
  6. 6.Coin changeMedium
  7. 7.Word breakHard
  8. 8.Longest common subsequenceHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.