Inventory Allocation by Bid Priority
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Inventory Allocation by Bid Priority
You run a fulfillment system that distributes a limited pool of identical items among competing customer requests. Each customer submits a single request to buy some quantity of the item, along with the price they are willing to pay per item (their bid) and the time their request arrived.
Allocate the available inventory one item at a time according to the rules below, then report which customers end up with **nothing**.
## Input
- `requests`: a list of requests, where each request is `[customerId, quantity, bidAmount, timestamp]`.
- `customerId` — a unique integer identifying the customer.
- `quantity` — the number of items this customer wants (a positive integer).
- `bidAmount` — the price per item this customer bids (a positive integer); a higher value means higher priority.
- `timestamp` — the integer arrival time of the request; smaller means earlier.
- `totalInventory`: a non-negative integer, the total number of identical items available to distribute.
Each `customerId` appears in at most one request.
## Allocation rules
1. **Bid priority.** Customers with a higher `bidAmount` are served before customers with a lower `bidAmount`. All requests at a given bid level are completely processed (until they are all satisfied or the inventory runs out) before any request at a strictly lower bid level is considered.
2. **Round-robin within a bid level.** Among the customers who share the same `bidAmount`, serve them in **round-robin** order, where the order within a round is by **increasing `timestamp`** (you may assume timestamps within the same bid level are distinct). In each round, every still-unsatisfied customer at this bid level receives **at most one** item, in timestamp order.
3. Keep running rounds at the current bid level until either every customer at that level has received their full requested `quantity`, or the inventory is exhausted. Then move on to the next lower bid level.
4. The moment the inventory reaches zero, allocation stops; any remaining customers (at the current bid level or any lower one) receive nothing.
A customer is said to "receive no items" if they were allocated zero items by the time the process ends (whether because the inventory ran out before reaching them, or it ran out during an earlier round before they got their first item).
## Output
Return the list of `customerId` values of every customer who received **zero** items. The order of the returned IDs does not matter unless your environment specifies otherwise; if an order is required, return them sorted in ascending order.
## Example
```
requests = [
[1, 5, 5, 0],
[2, 7, 8, 1],
[3, 7, 5, 1],
[4, 10, 3, 3]
]
totalInventory = 18
Output: [4]
```
**Walkthrough.**
- Bid level **8** (highest): only customer `2`, wanting 7 items. Round-robin with a single customer just hands them one item per round until satisfied. Customer `2` receives all 7. Inventory left: `18 - 7 = 11`.
- Bid level **5**: customers `1` (qty 5, timestamp 0) and `3` (qty 7, timestamp 1), served in timestamp order each round. Eleven items are split one-at-a-time: customer `1` reaches their full 5, and customer `3` receives the remaining 6 (one short of their requested 7) before inventory hits zero. Both received at least one item. Inventory left: `0`.
- Bid level **3**: customer `4` wants 10 items, but the inventory is already exhausted, so they receive nothing.
Only customer `4` receives zero items, so the answer is `[4]`.
## Constraints
- `1 <= len(requests)`.
- `1 <= quantity` for every request.
- `1 <= bidAmount` for every request.
- `0 <= totalInventory`.
- Timestamps within the same bid level are distinct.
- Your solution should handle the case where the inventory is large relative to demand (everyone is fully satisfied and the answer is empty) and the case where the inventory is zero (every customer receives nothing).
Quick Answer: This question assesses simulation and priority-queue design skills, requiring careful implementation of tiered, round-robin resource allocation under multiple ordering rules. It is a common coding-interview format for evaluating how well someone translates a multi-step, rule-heavy specification into correct, edge-case-aware logic. The domain is algorithmic simulation, testing practical application rather than abstract theory.
You run a fulfillment system that distributes a limited pool of identical items among competing customer requests. Each customer submits one request `[customerId, quantity, bidAmount, timestamp]`: the quantity they want, the price per item they bid (higher = higher priority), and the integer arrival time of the request. You are also given `totalInventory`, a non-negative integer count of identical items to distribute.
Allocate the inventory one item at a time by these rules:
1. Bid priority: customers with a higher `bidAmount` are served completely (all satisfied or inventory exhausted) before any customer at a strictly lower bid level.
2. Round-robin within a bid level: among customers sharing the same `bidAmount`, process them in rounds in increasing-`timestamp` order (timestamps within a bid level are distinct). In each round, every still-unsatisfied customer at that level receives at most one item, in timestamp order.
3. Keep running rounds at the current bid level until every customer there has their full requested `quantity` or the inventory is exhausted, then move to the next lower bid level.
4. The moment inventory reaches zero, allocation stops; anyone not yet served receives nothing.
Return the list of `customerId` values of every customer who received **zero** items (order does not matter).
Example: `requests = [[1,5,5,0],[2,7,8,1],[3,7,5,1],[4,10,3,3]]`, `totalInventory = 18`. Bid 8 gives customer 2 all 7 (11 left). Bid 5 gives customer 1 all 5 and customer 3 six of seven, exhausting inventory. Bid 3 (customer 4) gets nothing. Output: `[4]`.
Constraints
- 1 <= len(requests)
- 1 <= quantity for every request
- 1 <= bidAmount for every request
- 0 <= totalInventory
- Each customerId appears in at most one request
- Timestamps within the same bid level are distinct
Examples
Input: ([[1, 5, 5, 0], [2, 7, 8, 1], [3, 7, 5, 1], [4, 10, 3, 3]], 18)
Expected Output: [4]
Explanation: Bid 8: customer 2 gets all 7 (11 left). Bid 5: customer 1 gets 5, customer 3 gets 6 of 7 (inventory hits 0). Bid 3: customer 4 gets nothing. Only 4 is empty.
Input: ([[1, 5, 5, 0], [2, 3, 8, 1]], 0)
Expected Output: [1, 2]
Explanation: Inventory is zero, so allocation never starts and every customer receives nothing.
Input: ([[1, 5, 5, 0], [2, 3, 8, 1]], 100)
Expected Output: []
Explanation: Inventory (100) exceeds total demand (8), so both customers are fully satisfied and no one is left empty.
Input: ([[1, 1, 5, 0], [2, 1, 5, 1], [3, 1, 5, 2]], 2)
Expected Output: [3]
Explanation: Same bid level, one item each in timestamp order: customer 1 then customer 2 are served, inventory hits 0 before reaching customer 3.
Input: ([[1, 3, 10, 0], [2, 5, 5, 1]], 3)
Expected Output: [2]
Explanation: The higher bid (customer 1) consumes all 3 items; the lower-bid customer 2 gets nothing.
Input: ([[7, 10, 4, 5]], 4)
Expected Output: []
Explanation: A lone customer is partially filled with 4 of 10 items — nonzero, so the empty-list answer is empty.
Hints
- Group requests by bidAmount, then process the groups from the highest bid down to the lowest, stopping entirely once inventory hits zero.
- Within a bid group, sort by timestamp and simulate rounds: each round, walk customers in timestamp order giving one item to anyone not yet fully satisfied.
- A round that hands out no items means the level is either fully satisfied or blocked by empty inventory — end the level then. Track a per-customer allocated count and return the ids whose count is still 0.