Amazon OA Interview Question: Reduce Gifts

Question 1

New Year’s Day is around the corner and Amazon is having a sale. They have a list of items they are considering but they need to remove some of them. Determine the minimum number of items to remove from an array of prices so that the sum of prices of any k items does not exceed a threshold.

Note: If the number of items in the list is less than k, then there is no need to remove any items.

Function Description

Complete the function reduceGifts in the editor below.

reduceGifts has the following parameters:

• int prices[n]: the prices of each item
• int k: the number of items to sum
• int threshold: the maximum price of k items

Returns

int: the minimum number of items to remove from the list

Constraints

• 1 ≤ k ≤ n ≤ 10^5
• 1 ≤ threshold ≤ 10^9
• 1 ≤ prices[i] ≤ 10^9

Sample Case 0

Sample Input For Custom Testing

prices = [9, 6, 7, 2, 7, 2]
k = 2
threshold = 13

Sample Output

2

Explanation

Items with prices 9 and 7 have a sum larger than 13. After removing these two items, prices = [6, 7, 2, 7, 2]. No k items have a sum of prices greater than threshold.

This problem asks for the minimum number of items to remove so that the sum of any chosen group of k items does not exceed the threshold. The usual approach is to sort the prices and scan with a greedy strategy, checking sums of size k and removing the largest offending items when necessary. The main skills tested are sorting, greedy reasoning, and efficient handling of large constraints.