How should I practice Compute Lowest Linking (Connection) Expense?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Compute Lowest Linking (Connection) Expense associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Prefix Sum

Compute Lowest Linking (Connection) Expense

Learn this problem

● HardAmazonFULLTIMEOA

See Amazon hiring insights

Problem statement

Within 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 (using 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 (with 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.

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.

Each query is independent; the additional hubs deployed for one query do not persist for subsequent queries.

Function

getMinConnectionCost(storageLimit: int[], q: int, extraHubs: int[][]) → long[]

Complete the function getMinConnectionCost with 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 is a pair of integers denoting the positions of the two additional distribution hubs for a query.

Returns:

long int[q]: the minimum total connection cost for each query.

Examples

Example 1

storageLimit = [3, 6, 10, 15, 20]q = 1extraHubs = [[2, 4]]return = [8]

In this scenario, there exists q = 1 inquiry featuring two supplementary high-capacity dispatch hubs positioned at hubX = 2 and hubY = 4. After deploying the extra distribution hubs at indexes hubX = 2 and hubY = 4, the resulting connections and costs are determined as follows: The first depot links to the closest reachable dispatch hub at position 2, accumulating a cost of 6 - 3 = 3. The second depot operates as a dispatch hub itself, leading to zero cost. The third depot connects to the nearest accessible dispatch hub located at 4, generating a cost of 15 - 10 = 5. Both the fourth and fifth depots are either distribution hubs themselves or directly connected, contributing 0 + 0 = 0 cost. In conclusion, the total connection expense is calculated as (6 - 3) + (0) + (15 - 10) + (0) + (0) = 8. Thus, the resulting output is [8] for this query.

Example 2

storageLimit = [0, 2, 5, 9, 12, 18]q = 2extraHubs = [[2, 5], [1, 3]]return = [12, 18]

Clarification - In this scenario, we are given n = 6, with storageLimit = [0, 2, 5, 9, 12, 18], and q = 2 inquiries where extraHubs = [[2, 5], [1, 3]]. At the start, there’s a single primary dispatch hub located at depot number n. Therefore, the total initial linking cost amounts to (18 - 0) + (18 - 2) + (18 - 5) + (18 - 9) + (18 - 12) + (18 - 18) = 62. For the first inquiry, two temporary distribution hubs are deployed at positions 2 and 5. The connections and costs unfold as follows: The 1st depot connects to the closest available hub at position 2, generating a cost of 2 - 0 = 2. The 2nd depot acts as a dispatch hub itself, contributing 0 to the cost. The 3rd depot connects to the nearest dispatch hub at 5, yielding a cost of 12 - 5 = 7. The 4th depot links to the nearest hub at 5, causing a cost of 12 - 9 = 3. The 5th depot serves as a hub itself, resulting in zero cost. The 6th depot is also a hub, adding zero to the expense. Hence, the cumulative connection cost becomes 2 + 0 + 7 + 3 + 0 + 0 = 12. Moving to the second inquiry, two more high-performance distribution hubs are set up at positions 1 and 3. The cost breakdown is: The 1st depot is a hub itself, so cost incurred is 0. The 2nd depot connects to the closest available hub at 3, resulting in a cost of 5 - 2 = 3. The 3rd depot operates as a hub itself, so cost is 0. The 4th depot links to the closest hub at 6, adding a cost of 18 - 9 = 9. The 5th depot connects to the nearest hub at 6, with a cost of 18 - 12 = 6. The 6th depot serves as a hub itself, contributing 0 cost. Therefore, the total expense in this inquiry amounts to 0 + 3 + 0 + 9 + 6 + 0 = 18. The final output is [12, 18].

Example 3

storageLimit = [2, 6, 8, 14]q = 1extraHubs = [[1, 2]]return = [6]

In this situation, we are given n = 4 with storageLimit = [2, 6, 8, 14], and q = 1 inquiry where extraHubs = [[1, 2]]. At the start, there exists only a single central dispatch hub stationed at depot number 4. Therefore, the total connection distance is computed as (14 - 2) + (14 - 6) + (14 - 8) + (14 - 14) = 26. For the first inquiry, two temporary high-capacity dispatch hubs are established at indices 1 and 2. The resulting connections and incurred costs are as follows: The first depot functions as a distribution hub itself, leading to zero expense. The second depot also serves as a dispatch hub, hence zero expense. The third depot links to the closest accessible hub located at index 4, producing a cost of 14 - 8 = 6. The fourth depot acts as a hub itself, yielding zero expense. Summing up, the total connection expenditure equals 0 + 0 + 6 + 0 = 6. As a result, the output for this inquiry becomes [6].

Constraints

warehouseCapacity is given in non-decreasing order (each element is greater than or equal to the previous).
The array uses 1-based indexing.
For each query, the two additional hub positions satisfy 1 <= hubA < hubB <= n.
A warehouse at position i may only connect to a hub at position j where j >= i.
A central distribution hub is always present at position n.
Each query is independent; deployments do not persist across queries.
The connection cost for connecting warehouse i to hub j is warehouseCapacity[j] - warehouseCapacity[i].
The result for each query may exceed 32-bit integer range and must be returned as a long.