Katkat
Back

Circular Drone Hub Delivery Route

AmazonSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.