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