FastPrepBellman-Ford Route Costs With Credits
Problems/Bellman-Ford Route Costs With Credits

Bellman-Ford Route Costs With Credits

DoorDash logoDoorDash● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: A DoorDash machine learning engineer onsite report names Bellman-Ford as the topic of its coding round. The candidate did not get it working in the interview.

The report does not describe the task or what the interviewer expected, so the details here are practice choices. You find the cheapest cost from one start hub to every hub. Roads are one-way, with costs from -10^4 to 10^4. There are up to 200 hubs and 2000 roads. A hub you cannot reach gets 1000000000, and a negative cycle that the start can reach makes the answer an empty array. Two hubs can share several roads, a road can loop back to its own hub, and a negative cycle the start cannot reach is ignored.

The judged task matches the report at about 50%.

DoorDash plans delivery routes between n hubs, labeled 0 to n - 1. Each road is one-way and is given as roads[i] = [from, to, cost]. A cost can be negative: some roads come with a credit, so taking them lowers your total.

You start at hub start. The cost of a route is the sum of the costs of its roads. A route may pass through the same hub more than once.

Return an array dist of length n, where dist[i] is the lowest cost of any route from start to hub i.

  • Staying at start is a route with cost 0.
  • If no route reaches hub i, set dist[i] = 1000000000.
  • A negative cycle is a loop of roads whose total cost is below 0. If start can reach a negative cycle, you could go around it again and again and the cost would keep dropping. In that case, return an empty array. A negative cycle that start cannot reach does not change the answer.

Two hubs can be joined by several roads, and a road can start and end at the same hub.

Function

shortestRouteCosts(n: int, roads: int[][], start: int) → int[]

Examples

Example 1

n = 4roads = [[0,1,4],[0,2,5],[2,1,-3],[1,3,2],[2,3,6]]start = 0return = [0,2,5,4]

The direct road to hub 1 costs 4. Going 0 → 2 → 1 costs 5 + (-3) = 2, which is cheaper, so dist[1] = 2.

Hub 3 is reached by 0 → 2 → 1 → 3 for 2 + 2 = 4. The road 2 → 3 gives 5 + 6 = 11, which is worse.

Hub 2 costs 5. The answer is [0, 2, 5, 4].

Example 2

n = 4roads = [[0,1,3],[2,3,-4],[3,2,1]]start = 0return = [0,3,1000000000,1000000000]

From hub 0 you can only reach hub 1, for a cost of 3.

Hubs 2 and 3 form the loop 2 → 3 → 2 with total cost -4 + 1 = -3. That is a negative cycle, but hub 0 cannot reach it, so it does not matter. Hubs 2 and 3 are unreachable and get 1000000000.

Example 3

n = 3roads = [[0,1,1],[1,2,-1],[2,1,-1]]start = 0return = []

Hub 0 reaches hub 1, and the loop 1 → 2 → 1 costs -1 + (-1) = -2.

Each extra trip around the loop lowers the cost by 2, so there is no lowest cost. The loop is reachable from hub 0, so the answer is an empty array.

Constraints

  • 1 <= n <= 200
  • 0 <= roads.length <= 2000
  • roads[i].length == 3
  • roads[i] = [from, to, cost] with 0 <= from, to < n
  • -10^4 <= cost <= 10^4
  • 0 <= start < n

More DoorDash problems

  • Customer Bootstrap APIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Dasher Pay with Store Waits and Peak HoursPHONE SCREEN · Seen Nov 2026
  • Random Dasher Set OperationsONSITE INTERVIEW · Seen Nov 2026
All DoorDash interview questionsSee DoorDash hiring insights
Saved
public int[] shortestRouteCosts(int n, int[][] roads, int start) {
    // Write your code here.
}
Checking account…