Katkat
Back

Minimum Drone Delivery Time on a Ring of Hubs

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to calculate optimal traversal distances on a circular path, requiring the application of modular arithmetic and greedy logic to minimize movement between sequential points.

Problem Description

You are building an automated delivery system for a circular warehouse ring that contains n hubs, indexed 0 to n-1 in clockwise order. The distance between adjacent hubs i and (i + 1) % n is exactly 1 unit.

You are given a sequence of delivery requests as an array requests where each element is an integer representing the target hub index. Starting at hub 0, you must visit every requested hub in the order they appear in the array. For each request, you can travel either clockwise or counter-clockwise to reach the target hub.

Your task is to find the minimum total distance traveled to complete all deliveries in the given sequence.

Function Signature

def min_delivery_time(n: int, requests: List[int]) -> int:

Constraints

  • n: Number of hubs, 2 <= n <= 10^5
  • requests: 1 <= len(requests) <= 10^5
  • requests[i]: 0 <= requests[i] < n

Example 1

Input: n = 5, requests = [1, 4] Output: 2 Explanation: Start at 0. To reach 1 (clockwise: 1, counter-clockwise: 4), distance is 1. From 1 to 4 (clockwise: 3, counter-clockwise: 2), distance is 2. Total distance is 1 + 2 = 3. Wait, specifically: 0 -> 1 is 1 step. 1 -> 4 is 2 steps counter-clockwise. Total 3.

Example 2

Input: n = 10, requests = [9, 1] Output: 2 Explanation: Start at 0. To reach 9 (counter-clockwise), distance is 1. From 9 to 1 (clockwise), distance is 2. Wait, 9 to 1 is 2 steps clockwise (9->0->1). Total 1 + 2 = 3.

Edge Cases

  • The sequence starts from index 0.
  • If a target is the current hub, the distance is 0.
  • Moving to an adjacent hub can be done in 1 step regardless of direction if n=2.

Hints

Hint 1

For any two hubs `a` and `b`, the distance between them on a ring of size `n` is `min(|a - b|, n - |a - b|)`.

Hint 2

Maintain a variable `current_pos` initialized to 0 and iterate through the `requests` list, adding the minimal distance to a running sum.

Hint 3

Ensure your modular arithmetic correctly handles the wrap-around case by using `abs(a - b)` and `n - abs(a - b)`.

Follow-up questions

  • What if the drone can carry multiple packages and we want to reorder the requests to minimize the total travel distance?
  • How would the solution change if some hubs were 'blocked' and could not be traversed through?
  • If the distance between adjacent hubs was not uniform, how would you store the map to ensure efficient lookups?