FastPrep
Problem · Sorting

Use Minimum Tokens

● HardAmazonNEW GRADOA
See Amazon hiring insights

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 i is 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 Description

    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
    01 · Example 1
    warehouse = [2, 4, 1, 3]
catalog = [[5, 7]]
return = [TO-DO]
    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.
    02 · Example 2
    warehouse = [5, 1, 1, 4]
catalog = [[5, 7], [4, 10], [7, 9]]
return = [1, 3, 5]
    For the first shipment, the optimal selection is warehouse number four. You’ll need to spend one token to extend the capacity of the fourth warehouse to accommodate the shipment and no tokens on the other warehouses. The total tokens spent equal one for capacity augmentation + zero for backup storage = 1. For the second shipment, the optimal selection is either the second or third warehouse. You’ll spend three tokens to extend the capacity of the selected warehouse and no tokens on the remaining warehouses. Hence, the total tokens spent equal three for augmentation + zero for backup storage = 3. This explanation is incomplete. Will enhance it later.
    Constraints
    • 2 ≤ n ≤ 10^5
    • 1 ≤ warehouse[i] ≤ 10^9
    • 1 ≤ q ≤ 10^5
    • 1 ≤ catalog[i][0] ≤ 10^9
    • 1 ≤ catalog[i][1] ≤ 10^15
    More Amazon problems
    drafts saved locally
    public long[] useMinimumTokens(int[] warehouse, long[][] catalog) {
  // write your code here
}
    warehouse[2, 4, 1, 3]
    catalog[[5, 7]]
    expected[TO-DO]
    sign in to submit