Unfulfilled Bids after Ranked Round-Robin Allocation
Amazon● MediumCONTRACTOAProblem statement
You receive a fixed inventory and a list of customer bids. Each bid is represented as [customerId, bidAmount, quantity, bidPlacedAt].
Allocate inventory using these rules:
- Process higher
bidAmountvalues before lower ones. - Within one bid amount, order bids by increasing
bidPlacedAt, breaking a remaining tie by increasingcustomerId. - Allocate one unit to each still-unfulfilled bid in that order, then repeat another cycle for the same bid amount.
- Move to the next lower bid amount only after every bid in the current group is fulfilled or the inventory is exhausted.
Return the customerId of every bid that receives fewer units than its requested quantity. Return the IDs in increasing order.
Function
findUnfulfilledBids(bids: int[][], totalInventory: int) → int[]Examples
Example 1
bids = [[1,3,1,1],[2,4,2,2]]totalInventory = 1return = [1,2]Customer 2 receives the only unit because its bid amount is higher. Customer 1 receives zero of one requested unit, and customer 2 receives one of two requested units, so both bids are not fully fulfilled.
Example 2
bids = [[1,3,2,1],[2,3,2,2],[3,3,1,3]]totalInventory = 4return = [2]The first cycle gives one unit to customers 1, 2, and 3. The remaining unit goes to customer 1 at the start of the second cycle. Only customer 2 receives fewer units than requested.
Constraints
1 <= bids.length <= 2000- Every bid has exactly four integer fields.
1 <= customerId, bidAmount, quantity, bidPlacedAt <= 10^9- All
customerIdvalues are distinct. - The sum of all requested quantities is at most
200000. 0 <= totalInventory <= 200000