Amazon OA 面试真题解析：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.

这题要求从商品价格数组中删除尽可能少的元素，使得任意连续含义下的“任意 k 个商品价格之和”都不超过阈值。关键做法是先按价格排序，再从大到小检查长度为 k 的窗口：如果当前窗口和已经超过 threshold，就说明必须删除窗口中较大的元素之一；结合排序后的单调性，可以用贪心逐步统计最少删除数。由于 n 可达 10^5，通常需要 O(n log n) 的排序加线性扫描，适合面试中考察贪心与前缀 / 窗口维护能力。