Use Minimum Tokens
Updated
Problem statement
Amazon operates a system of n warehouses, each represented by warehouse[i], where warehouse[i] indicates the maximum number of items that particular warehouse can hold. Additionally, there are q shipments to process, represented by a 2D array catalog[i][2]. Each shipment has specific requirements:
catalog[i][0]denotes the minimum capacity that the selected warehouse must have to accommodate the shipment.catalog[i][1]denotes the minimum combined capacity required from the other warehouses to fulfill backup storage needs.
Amazon can increase the capacity of any warehouse by spending 1 token per unit of capacity.
The task is to determine the optimal strategy for allocating capacity for each shipment such that the fewest number of tokens are expended. This strategy must ensure that the selected warehouse meets the required capacity for the shipment and that the combined capacity of the other warehouses is sufficient for backup storage.
Note
- The tokens are spent independently for each shipment
- If warehouse
iis selected to accommodate the shipment and if there are some left over capacity (i.e.,warehouse[i] - catalog[i][0] > 0) then it cannot be used for backup storage.
Function
useMinimumTokens(warehouse: int[], catalog: long[][]) → long[]
Complete the function useMinimumTokens in the editor.
useMinimumTokens has the following parameters:
int warehouse[n]: an array listing the initial maximum capacity of each warehouse.long catalog[q][2]: A 2D array describing the shipments.
Returns
long[q]: An array representing the minimum number of tokens needed to serve each shipment while ensuring sufficient backup storage.
Examples
Example 1
warehouse = [2, 4, 1, 3]catalog = [[5, 7]]return = [2]If the first warehouse is expanded for the shipment, 3 tokens are needed for the first warehouse to accommodate the shipment, and no tokens are needed for the rest of the warehouses to maintain backup storage. Hence, the total tokens needed = 3 + 0 = 3. If the second warehouse is expanded for the shipment, 1 token is needed for the second warehouse to accommodate the shipment, and 1 token is needed for the rest of the warehouses to maintain backup storage. Hence, the total tokens needed = 1 + 1 = 2. If the third warehouse is expanded for the shipment, 4 tokens are needed for the third warehouse to accommodate the shipment, and no tokens are needed for the rest of the warehouses to maintain backup storage. Hence, the total tokens needed = 4 + 0 = 4. If the fourth warehouse is expanded for the shipment, 2 tokens are needed for the fourth warehouse to accommodate the shipment, and no tokens are needed for the rest of the warehouses to maintain backup storage. Hence, the total tokens needed = 2 + 0 = 2.
Example 2
warehouse = [5, 1, 1, 4]catalog = [[5, 7], [4, 10], [7, 9]]return = [1, 3, 5]The warehouses hold 5 + 1 + 1 + 4 = 11 in total. If you pick a warehouse with capacity x, you pay max(0, need - x) to grow it, plus max(0, backup - (11 - x)) to grow the others.
- Shipment 1 (
[5, 7]): picking the warehouse with4costs1 + 0 = 1, and picking the one with5costs0 + 1 = 1. A warehouse with1costs4 + 0 = 4. The minimum is1. - Shipment 2 (
[4, 10]): a warehouse with1costs3 + 0 = 3, the one with4costs0 + 3 = 3, and the one with5costs0 + 4 = 4. The minimum is3. - Shipment 3 (
[7, 9]): the warehouse with5costs2 + 3 = 5, the one with4costs3 + 2 = 5, and one with1costs6 + 0 = 6. The minimum is5.
So the answer is [1, 3, 5].
Constraints
2 ≤ n ≤ 10^51 ≤ warehouse[i] ≤ 10^91 ≤ q ≤ 10^51 ≤ catalog[i][0] ≤ 10^91 ≤ catalog[i][1] ≤ 10^15
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Minimum Cost to Make Array EqualWalmart · OAWalmart interview questions
- Minimum Space Wasted From PackagingIMC Trading · OAIMC Trading interview questions
- Subscription and Usage-Based Billing CalculatorStripe · OAStripe interview questions
- Minimum Operations to Make All Array Elements EqualIBM · OAIBM interview questions
- Calculating QuantilesIndeed · OAIndeed interview questions
- Count Lamps Lighting Each PointCapital One · OACapital One interview questions
- Maintain a Consistent-Hashing RingCohesity · ONSITE INTERVIEW
- Maintain a Consistent-Hashing RingApple · PHONE SCREENApple interview questions
- Average Prices from Broker QuotesAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Sliding Window MedianAuxoAI · OA