AMAZON Coding Question – Solved

In Amazon's highly efficient logistics network, minimizing operational overhead and optimizing package routing is crucial to ensure smooth deliveries across various regions. The network consists of n warehouses, numbered from 1 to n, each strategically positioned at its corresponding index. Each warehouse has a specific storage capacity, given by warehouseCapacity, where warehouseCapacity[i] represents the capacity of the warehouse located at position i (assuming 1-based indexing). These warehouses are organized in a non-decreasing order of their storage capacities, meaning each warehouse's storage capacity is greater than or equal to the one before it. Each warehouse must establish a connection to a distribution hub positioned at a location greater than or equal to its own. This means that a warehouse at position i can only connect to a hub at position j where j ≥ i. To optimize inventory routing, Amazon has placed a central high-capacity distribution hub at the last warehouse, located at position n. This hub serves as the main connection point for all warehouses if necessary. The cost of establishing a connection from warehouse at i to a hub at position j is given by warehouseCapacity[j] - warehouseCapacity[i]. Given q queries of the form (hubA, hubB), where two additional high-performance distribution hubs are deployed at warehouses hubA and hubB (1 ≤ hubA < hubB < n), the goal is to calculate the minimum total connection cost for all warehouses, considering the nearest available distribution hub at or beyond each warehouse's position. Note: - The problem statement assumes 1-based indexing for the warehouseCapacity array. - Each query is independent, i.e., the changes made do not persist for subsequent queries. - Each warehouse connects to the nearest hub at or beyond its position (either hubA, hubB, or the central hub at n) to minimize the overall connection cost. Example: n = 5 warehouseCapacity = [3, 6, 10, 15, 20] additionalHubs = [[2, 4]] In this case there is q = 1 query with two additional high-performance distribution hubs at position hubA = 2 and hubB = 4. This diagram shows the calculation of the total connection cost before additional distribution hubs are considered: Once additional distribution hubs are installed at positions hubA = 2 and hubB = 4: - 1st warehouse will connect to the nearest available distribution hub at position 2, cost incurred = 6 - 3 = 3 - 2nd warehouse is itself a distribution hub, so cost incurred = 0 - 3rd warehouse will connect to the nearest available distribution hub at position 4, cost incurred = 15 - 10 = 5 - 4th and 5th warehouses are themselves distribution hubs, so cost incurred = 0 + 0 = 0 Thus, the total connection cost = (6 - 3) + (0) + (15 - 10) + (0) + (0) = 8. Hence, return [8] as the answer. Function Description: Complete the function getMinConnectionCost in the editor below. getMinConnectionCost has the following parameters: int warehouseCapacity[n]: a non-decreasing array of integers representing the storage capacities of the warehouses int additionalHubs[q][2]: an array where each element denotes the positions of two additional distribution hubs installed for a query Returns: long_int[q]: the answers for each query Constraints: - 3 ≤ n ≤ 1*10^5 - 1 ≤ q ≤ 1*10^5 - 3 ≤ n*q ≤ 1*10^9 - 0 ≤ warehouseCapacity[i] ≤ 10^9 - warehouseCapacity[i] ≤ warehouseCapacity[i + 1] for all 0 ≤ i < n - 1 - 1 ≤ additionalHubs[i][0] < additionalHubs[i][1] < n