Amazon OA SDE 2

Round 1

Questions: Determine the minimum number of items to remove from an array of prices so that the sum of k items does not exceed a given threshold.

• Input:
  • prices = {3,2,1,4,6,5}, k = 3, threshold = 14
  • Expected Output: 1
• Input:
  • prices = {9,6,7,2,7,2}, k = 2, threshold = 13
  • Expected Output: 2
• Input:
  • prices = {5, 5, 5, 5, 5, 5}, k = 4, threshold = 20
  • Expected Output: 0
• Input:
  • prices = {1, 1000000000, 1000000000, 1000000000}, k = 3, threshold = 3000000000
  • Expected Output: 0
• Input:
  • prices = {1, 2, 3, 4, 5}, k = 3, threshold = 15
  • Expected Output: 0
• Input:
  • prices = {10} * 100000, k = 50000, threshold = 450000
  • Expected Output: 0
• Input:
  • prices = {999999999, 999999999, 999999999, 1}, k = 3, threshold = 2999999998
  • Expected Output: 1
• Input:
  • prices = {1000000000} * 100000, k = 100000, threshold = 10^14
  • Expected Output: 1
• Input:
  • prices = {100, 200, 300, 400, 10000}, k = 3, threshold = 900
  • Expected Output: 1
• Input:
  • prices = {1, 2, 3, 50, 52}, k = 3, threshold = 100
  • Expected Output: 0
• Input:
  • prices = {10000}, k = 1, threshold = 10000
  • Expected Output: 0
• Input:
  • prices = {1, 2, 3, 4, 5, 6}, k = 3, threshold = 11
  • Expected Output: 2

Constraints:

• 1 <= k <= 10^5
• 1 <= threshold <= 10^9
• 1 <= prices[i] <= 10^9