Minimum Delivery Cost Between Cities
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Minimum Delivery Cost Between Cities
Implement `minimum_delivery_costs(delivery_charges, queries)`.
There are `n` cities indexed from `0` to `n - 1`, and city `i` has value `delivery_charges[i]`. A delivery can move from any city `i` to any different city `j`:
- The normal move cost is `abs(delivery_charges[i] - delivery_charges[j])`.
- If `j` is the unique city whose value is closest to city `i`'s value, the move from `i` to `j` instead costs `1`.
- If two or more cities tie for closest to `i`, city `i` has no discounted move.
A route may use intermediate cities. For each `(start, end)` query, return the minimum total cost to reach `end` from `start`.
## Constraints
- `2 <= n <= 2,000`
- All delivery charges are distinct signed 32-bit integers.
- `1 <= len(queries) <= 2,000`
- Query endpoints are valid city indices.
- Costs fit in signed 64-bit integers.
## Candidate clarifications
Confirm whether closest-city ties disable the discount, whether the cheap edge is directed, and whether routes may visit intermediate cities.
Quick Answer: This coding interview question evaluates cost optimization and routing over a city network with value-based moves and conditional directed discounts. It tests practical algorithm design, edge-case interpretation, and complexity analysis for repeated minimum-cost queries.
# Minimum Delivery Cost Between Cities
There are `n` cities indexed from `0` to `n - 1`. City `i` carries the value `delivery_charges[i]`, and all `n` values are distinct.
A single delivery move goes from a city `i` to any different city `j`:
- The normal move cost is `abs(delivery_charges[i] - delivery_charges[j])`.
- If `j` is the **unique** city whose value is closest to city `i`'s value, the move from `i` to `j` instead costs `1`.
- If two or more cities tie for closest to city `i`, then city `i` has **no** discounted move at all.
The discount is **directed**. It describes the move out of `i` toward `i`'s own unique nearest city, and says nothing about the move from `j` back to `i`, because `j`'s nearest city may be a different city entirely.
A route may pass through any number of intermediate cities, paying for every move it makes.
Implement `minimum_delivery_costs(delivery_charges, queries)`. For each `queries[q] = [start, end]`, compute the minimum total cost of a route from city `start` to city `end`, and return the answers as a list in the same order as `queries`. A query with `start == end` costs `0`.
## Examples
**Example 1**
```
Input: delivery_charges = [4, 7, 8, 15], queries = [[0, 3], [3, 0], [0, 1]]
Output: [9, 5, 1]
```
City `0` (value `4`) has `7` as its unique nearest value, so `0 -> 1` costs `1`.
City `1` (value `7`) is nearer to `8` than to `4`, so `1 -> 2` costs `1` while `1 -> 0` costs the normal `3`.
City `2` (value `8`) is nearer to `7` than to `15`, so `2 -> 1` costs `1` while `2 -> 3` costs the normal `7`.
City `3` (value `15`) has `8` as its unique nearest value, so `3 -> 2` costs `1`.
- `[0, 3]`: `0 -> 1` (`1`) + `1 -> 2` (`1`) + `2 -> 3` (`7`) = `9`, beating the direct move of `11`.
- `[3, 0]`: `3 -> 2` (`1`) + `2 -> 1` (`1`) + `1 -> 0` (`3`) = `5`. The same pair of cities in the other direction costs less, because the discounts are directed.
- `[0, 1]`: the single discounted move, `1`.
**Example 2**
```
Input: delivery_charges = [10, 20, 30], queries = [[1, 0], [1, 2], [0, 2]]
Output: [10, 10, 11]
```
City `1` (value `20`) is exactly `10` away from both `10` and `30`. Those two tie for closest, so city `1` gets no discount and both of its moves cost the normal `10`. Cities `0` and `2` each have `20` as their unique nearest value, so `0 -> 1` and `2 -> 1` cost `1`. Query `[0, 2]` therefore pays `1` to reach city `1` and then the normal `10` onward to city `2`, for `11`.
## Output format
Return a list of exactly `len(queries)` integers, in query order. Every answer is uniquely determined by the input, so exactly one output is correct.
## Note on integer width
Answers can exceed `2^31 - 1` (two cities at opposite ends of the signed 32-bit range are about `4.3 * 10^9` apart), so accumulate costs in a 64-bit integer type: `long` in Java, `long long` / `int64_t` in C++.
Constraints
- 2 <= n == len(delivery_charges) <= 2,000
- -2^31 <= delivery_charges[i] <= 2^31 - 1 (each value is a signed 32-bit integer)
- All values in delivery_charges are distinct
- 1 <= len(queries) <= 2,000
- queries[q] == [start, end] with 0 <= start <= n - 1 and 0 <= end <= n - 1; start may equal end
- Every answer fits in a signed 64-bit integer (answers can exceed 2^31 - 1, so use long / long long)
Examples
Input: ([4, 7, 8, 15], [[0, 3], [3, 0], [0, 1]])
Expected Output: [9, 5, 1]
Input: ([10, 20, 30], [[1, 0], [1, 2], [0, 2]])
Expected Output: [10, 10, 11]
Hints
- Every normal move costs an absolute difference, which is a distance on a number line. Ask yourself what a direct normal move from i to j buys you that a chain of normal moves through the cities lying between them does not.
- A city's closest city can only be one of the two cities immediately beside it once you sort by value, so every discounted move connects two cities that are adjacent in sorted order — and a tie is exactly the case where those two neighbours are equidistant.
- Once all the moves worth taking connect sorted neighbours, a query becomes a walk along a line that never needs to double back. Two prefix-sum arrays — one for the left-to-right cost of each adjacent step, one for right-to-left — answer every query in O(1) after sorting.