Katkat
Back

Minimum Delivery Cost Between Cities

UberSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to optimize pathfinding costs in a graph where edge weights are determined by a combination of absolute differences and conditional local minimums.

Problem Statement

You are given an array deliveryCharge of size n, where deliveryCharge[i] represents the base delivery cost of city i. A direct path exists between any two cities i and j with a cost calculated as follows:

  1. Standard Cost: abs(deliveryCharge[i] - deliveryCharge[j])
  2. Discounted Cost: If city j is the "nearest" city to city i (i.e., j is the index k that minimizes abs(deliveryCharge[i] - deliveryCharge[k]) for all k != i), the cost is 1. If there is a tie for the nearest city, no discounted cost applies.

Given an array queries where each query is [start, end], return an array of the minimum cost to travel from start to end for each query. You may travel through any number of intermediate cities.

Constraints

  • n <= 10^5
  • queries.length 2) = 1.
  • City 1 (val 5): Nearest is City 2 (val 2), diff=3. Cost(1->2) = 3.
  • City 2 (val 2): Nearest is City 0 (val 1), diff=1. Cost(2->0) = 1.
  • Path 0->1: Direct = abs(1-5) = 4. Path 0->2->1 = Cost(0->2) + Cost(2->1) = 1 + 3 = 4. Output: [4]

Edge Cases

  • Start equals end (cost 0).
  • n is small (e.g., 2).
  • Multiple cities having the same deliveryCharge (affects the 'unique' nearest neighbor condition).

Hints

Hint 1

Identify which cities have a 'unique' nearest neighbor by sorting the `deliveryCharge` array and comparing distances to immediate neighbors.

Hint 2

Model the problem as a shortest-path problem on a graph where most edges have weight `abs(diff)` and special edges have weight 1.

Hint 3

Notice that the path between any two nodes will never involve more than one 'discounted' hop or a sequence of direct `abs` differences that simplify into a single subtraction.

Follow-up questions

  • How would your approach change if the discounted cost 1 was only available during specific time windows?
  • What is the time complexity if you need to perform Q queries after pre-processing the graph?
  • If the 'nearest neighbor' discount could be used multiple times in a single path, how does this change the graph traversal requirements?