FastPrep
Problem · Simulation

Inventory Allocation

Learn this problem
● MediumAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

You are given a list of inventory requests. Each request is represented as [customerId, quantity, bidAmount, timestamp].

Allocate totalInventory items using these rules:

  • Requests with a higher bidAmount are processed before lower bids.
  • For requests with the same bidAmount, items are distributed in round-robin order by increasing timestamp.
  • During each round, a customer can receive at most one item.
  • A customer leaves the current round-robin group once their requested quantity is fulfilled.
  • Lower bids are considered only after every higher bid has either been fulfilled or inventory is exhausted.

Return the customer IDs of customers who receive no items, in the same order their requests appear in the input.

Function

getUnfulfilledCustomers(requests: int[][], totalInventory: int) → int[]

Complete the function getUnfulfilledCustomers.

  • int requests[n][4]: rows of [customerId, quantity, bidAmount, timestamp]
  • int totalInventory: the number of items available

Returns

int[]: customers who receive no items.

Examples

Example 1

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

Customer 2 is fully served first because bid 8 is highest. Customers 1 and 3 then share the remaining inventory at bid 5. No inventory remains for customer 4.

Example 2

requests = [[1,2,10,0],[2,3,10,1],[3,1,5,0]]totalInventory = 3return = [3]

The bid-10 group receives all 3 available items before the lower bid is considered, so customer 3 receives none.

Constraints

  • 1 <= requests.length <= 10^5
  • requests[i].length = 4
  • customer IDs are unique.
  • 0 <= timestamp <= 10^9
  • 0 <= totalInventory <= 10^9

More Amazon problems

drafts saved locally
public int[] getUnfulfilledCustomers(int[][] requests, int totalInventory) {
  // write your code here
}
requests[[1,5,5,0],[2,7,8,1],[3,7,5,1],[4,10,3,3]]
totalInventory18
expected[4]
checking account