Amazon OA 面试真题解析：Allocate Limited Inventory Items by Priority

Allocate limited inventory items based on a priority algorithm.

During a flash sale on Amazon, customers submit requests for a limited quantity of a product. Each request includes:

[customerId, quantity, bidAmount, timestamp]

Items are allocated using these rules:

• Higher bids get priority.
• If multiple customers have the same bid, allocate items in round-robin order based on the earliest timestamp until all inventory is allocated.
• A customer gets one item per round until their request is fulfilled.

Return the IDs of customers who received no items.

Note: Round-robin allocation means cycling through the tied customers in order of their timestamps, granting exactly one item to each customer per cycle, until either the inventory runs out or all requested quantities are fulfilled.

Example

Input:

requests = [[1, 5, 5, 0], [2, 7, 8, 1], [3, 7, 5, 1], [4, 10, 3, 3]]
totalInventory = 18

Output:

[4]

Explanation: The first three requests have a higher bidding amount than the 4th request, and the total quantity requested in the first three requests is 19, whereas the available inventory is 18, so only one customer is left without any allocation: customer ID 4.

这道题要求根据竞价和时间戳给有限库存做分配，核心是先按 bidAmount 降序处理，再在同一竞价组内按 timestamp 的先后顺序进行轮询分配，每轮每个客户最多拿 1 件，直到库存耗尽或所有请求满足。实现时通常先把请求按出价分组排序，再对每个组模拟 round-robin；如果某个客户最终没有分到任何商品，就把他的 customerId 加入结果。重点在于正确处理同 bid 的公平分配，以及判断哪些客户完全没有获得库存。