Circular Drone Hub Delivery Route
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
A drone delivery network is laid out as a **ring of `n` hubs**, numbered `0, 1, ..., n - 1`. Each hub is connected by a direct air corridor to its two neighbors on the ring, and the ring closes back on itself: hub `n - 1` connects directly to hub `0`. There are no shortcuts across the middle of the ring — a drone can only fly along corridors between adjacent hubs.
You are given an integer array `corridor` of length `n`, where `corridor[i]` is the length of the air corridor connecting hub `i` and hub `(i + 1) % n`. A drone may fly along the ring in either direction:
- **Clockwise**, moving from a hub to the next-higher index (wrapping from `n - 1` back to `0`).
- **Counterclockwise**, moving from a hub to the next-lower index (wrapping from `0` back to `n - 1`).
The cost of crossing a corridor equals its length, regardless of direction.
A delivery drone must complete a route given as an array `route` of `m` hub indices. The drone starts at `route[0]`, then flies to `route[1]`, `route[2]`, ..., `route[m - 1]` in exactly the given order (it is not allowed to reorder stops). For each leg from the current hub to the next hub, the drone takes the **shorter** of the two possible arcs around the ring (clockwise or counterclockwise). If the two arcs are equal in length, either may be taken at no difference in cost. A leg whose two endpoints are the same hub has cost `0`.
Return the **total distance** the drone flies to complete the entire route.
### Input Format
- Line 1: an integer `n`, the number of hubs.
- Line 2: `n` space-separated integers, `corridor[0], corridor[1], ..., corridor[n - 1]`.
- Line 3: an integer `m`, the number of stops in the route.
- Line 4: `m` space-separated integers, the route (each value is a hub index in `[0, n - 1]`).
### Output Format
- A single integer: the total minimum distance flown over all legs of the route.
### Constraints
- `2 <= n <= 10^5`
- `1 <= corridor[i] <= 10^4`
- `1 <= m <= 10^5`
- `0 <= route[j] <= n - 1`
- Consecutive entries in `route` may be equal (such a leg contributes `0`).
- The answer can exceed 32-bit range; use 64-bit integers.
### Example 1
```
Input:
4
1 2 3 4
3
0 2 3
Output:
6
```
Explanation: The ring corridors have lengths `[1, 2, 3, 4]`, so the full loop measures `1 + 2 + 3 + 4 = 10`.
- Leg `0 -> 2`: clockwise arc is `corridor[0] + corridor[1] = 1 + 2 = 3`; counterclockwise arc is `10 - 3 = 7`. Shorter is `3`.
- Leg `2 -> 3`: clockwise arc is `corridor[2] = 3`; counterclockwise arc is `10 - 3 = 7`. Shorter is `3`.
Total distance is `3 + 3 = 6`.
### Example 2
```
Input:
4
1 2 3 4
2
1 3
Output:
5
```
Explanation: The clockwise arc from hub `1` to hub `3` is `corridor[1] + corridor[2] = 2 + 3 = 5`; the counterclockwise arc is `10 - 5 = 5`. Both arcs are equal, so the leg costs `5`. There is only one leg, so the total is `5`.
### Example 3
```
Input:
3
4 4 4
4
0 1 1 0
Output:
8
```
Explanation: The full loop measures `12`.
- Leg `0 -> 1`: shorter arc is `4`.
- Leg `1 -> 1`: same hub, cost `0`.
- Leg `1 -> 0`: shorter arc is `4`.
Total distance is `4 + 0 + 4 = 8`.
Quick Answer: This question evaluates a candidate's ability to work with circular array structures and prefix sums to compute shortest distances on a ring topology. It tests practical coding skill in efficiently handling wraparound arithmetic and cumulative sums, a common pattern in algorithm interviews assessing array manipulation and optimization under scale constraints.
A drone delivery network is laid out as a **ring of `n` hubs**, numbered `0, 1, ..., n - 1`. Each hub is connected by a direct air corridor to its two neighbors on the ring, and the ring closes back on itself: hub `n - 1` connects directly to hub `0`. There are no shortcuts across the middle of the ring — a drone can only fly along corridors between adjacent hubs.
You are given an integer array `corridor` of length `n`, where `corridor[i]` is the length of the air corridor connecting hub `i` and hub `(i + 1) % n`. A drone may fly along the ring in either direction:
- **Clockwise**, moving from a hub to the next-higher index (wrapping from `n - 1` back to `0`).
- **Counterclockwise**, moving from a hub to the next-lower index (wrapping from `0` back to `n - 1`).
The cost of crossing a corridor equals its length, regardless of direction.
A delivery drone must complete a route given as an array `route` of `m` hub indices. The drone starts at `route[0]`, then flies to `route[1]`, `route[2]`, ..., `route[m - 1]` in exactly the given order (it is not allowed to reorder stops). For each leg from the current hub to the next hub, the drone takes the **shorter** of the two possible arcs around the ring (clockwise or counterclockwise). If the two arcs are equal in length, either may be taken at no difference in cost. A leg whose two endpoints are the same hub has cost `0`.
Return the **total distance** the drone flies to complete the entire route.
Your function receives two arguments: `corridor` (the length-`n` array of corridor lengths) and `route` (the length-`m` array of hub indices to visit in order). Return a single integer — the total minimum distance flown over all legs.
### Example 1
```
corridor = [1, 2, 3, 4], route = [0, 2, 3] -> 6
```
The full loop measures `1 + 2 + 3 + 4 = 10`.
- Leg `0 -> 2`: clockwise arc `corridor[0] + corridor[1] = 3`; counterclockwise `10 - 3 = 7`. Shorter is `3`.
- Leg `2 -> 3`: clockwise arc `corridor[2] = 3`; counterclockwise `7`. Shorter is `3`.
Total `= 3 + 3 = 6`.
### Example 2
```
corridor = [1, 2, 3, 4], route = [1, 3] -> 5
```
Clockwise arc from hub `1` to hub `3` is `2 + 3 = 5`; counterclockwise is also `5`. Both arcs are equal, so the leg costs `5`.
### Example 3
```
corridor = [4, 4, 4], route = [0, 1, 1, 0] -> 8
```
The full loop measures `12`. Leg `0 -> 1` is `4`, leg `1 -> 1` is `0` (same hub), leg `1 -> 0` is `4`. Total `= 8`.
### Constraints
- `2 <= n <= 10^5`
- `1 <= corridor[i] <= 10^4`
- `1 <= m <= 10^5`
- `0 <= route[j] <= n - 1`
- Consecutive entries in `route` may be equal (such a leg contributes `0`).
- The answer can exceed 32-bit range; use 64-bit integers.
Constraints
- 2 <= n <= 10^5
- 1 <= corridor[i] <= 10^4
- 1 <= m <= 10^5
- 0 <= route[j] <= n - 1
- Consecutive route entries may be equal (a same-hub leg contributes 0).
- The answer can exceed 32-bit range; use 64-bit integers.
Examples
Input: ([1, 2, 3, 4], [0, 2, 3])
Expected Output: 6
Explanation: Loop length 10. Leg 0->2 costs min(3, 7) = 3; leg 2->3 costs min(3, 7) = 3. Total 6.
Input: ([1, 2, 3, 4], [1, 3])
Expected Output: 5
Explanation: The two arcs from hub 1 to hub 3 are both 5, so the single leg costs 5.
Hints
- Build a prefix-sum array over corridor so the clockwise distance between any two hubs is a single subtraction. Let prefix[0] = 0 and prefix[i+1] = prefix[i] + corridor[i]; then total = prefix[n] is the full loop length.
- For a leg between hubs a and b, let lo = min(a, b) and hi = max(a, b). One arc has length prefix[hi] - prefix[lo]; the other is total - that. Add min(arc, total - arc) for each leg.
- A same-hub leg gives arc = 0, so min(0, total) = 0 handles it automatically. Accumulate into a 64-bit integer since m legs of up to (n * 10^4)/2 each can overflow 32 bits.