Compute Total Manual Distance
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A package must be delivered on a one-dimensional line from position `0` to position `target`.
You are given an array `stations`, where each element is the position of a charging station.
A drone can only take off from a charging station, and each flight can move the package forward by at most `10` units. After the drone lands, the package's position becomes the landing position.
The delivery process is fixed and repeats until the package reaches `target`:
1. Let `current` be the package's current position.
2. Find the nearest charging station at or ahead of `current`, meaning the minimum station position `s` such that `s >= current`.
3. A human carries the package from `current` to `s`. This adds `s - current` to the manual carrying distance.
4. The drone launches from `s` and flies forward as far as possible, up to `10` units, without passing the target. The new package position becomes `min(s + 10, target)`.
Return the total distance the package is carried manually.
You may assume the process is always feasible. If `stations` is not sorted, your algorithm should handle that.
Quick Answer: This question evaluates array processing, state simulation, and algorithmic reasoning for deterministic stepwise processes, including handling unsorted inputs and edge cases in distance computations.
A package must be delivered on a one-dimensional line from position 0 to position target.
You are given an array stations, where each element is the position of a charging station.
A drone can only take off from a charging station, and each flight can move the package forward by at most 10 units. After the drone lands, the package's position becomes the landing position.
The delivery process is fixed and repeats until the package reaches target:
1. Let current be the package's current position.
2. Find the nearest charging station at or ahead of current, meaning the minimum station position s such that s >= current.
3. A human carries the package from current to s. This adds s - current to the manual carrying distance.
4. The drone launches from s and flies forward as far as possible, up to 10 units, without passing the target. The new package position becomes min(s + 10, target).
Return the total distance the package is carried manually.
If stations is not sorted, your algorithm should handle that. You may assume the process is always feasible.
Constraints
- 0 <= len(stations) <= 200000
- -10^9 <= stations[i] <= 10^9
- 0 <= target <= 10^9
- stations may be unsorted and may contain duplicates
- The described process is always feasible
Examples
Input: ([0, 7, 20], 25)
Expected Output: 10
Explanation: Start at 0, use station 0, fly to 10. Then the nearest station at or ahead of 10 is 20, so the human carries the package 10 units from 10 to 20. The drone then reaches 25. Total manual distance = 10.
Input: ([18, 0, 6, 31, 12], 40)
Expected Output: 11
Explanation: After sorting: [0, 6, 12, 18, 31]. Use 0 -> fly to 10, then use 12 (manual +2) -> fly to 22, then use 31 (manual +9) -> fly to 40. Total = 11.
Input: ([10, 0, 10, 20], 30)
Expected Output: 0
Explanation: The package always lands exactly on a station: 0 -> 10 -> 20 -> 30. No manual carrying is needed.
Input: ([-5, 24, 3, 14], 30)
Expected Output: 4
Explanation: After sorting: [-5, 3, 14, 24]. Station -5 is behind the start and is ignored. Use 3 (manual +3) -> fly to 13, then use 14 (manual +1) -> fly to 24, then use 24 (manual +0) -> fly to 30. Total = 4.
Input: ([], 0)
Expected Output: 0
Explanation: The package already starts at the target, so no movement is needed.
Input: ([5], 12)
Expected Output: 5
Explanation: The human carries the package from 0 to 5, then the drone flies from 5 to 12. Total manual distance = 5.
Hints
- Sort the station positions first. Then the nearest station at or ahead of the current position can be found by moving a single pointer forward.
- After using a station at position s, the next current position becomes min(s + 10, target). Since current only moves forward, each station is considered at most once.