FastPrep
Problem · Graph

Shortest Path with Mandatory Waypoint

● MediumGoogleFULLTIMEONSITE INTERVIEW
See Google hiring insights

You are given a weighted graph with n nodes labeled 0 through n - 1. Each edge is represented as [u, v, w], meaning there is an edge between nodes u and v with non-negative distance w.

Compute two values:

  1. the length of the shortest path from start to target
  2. the length of the shortest path from start to target that must pass through waypoint

If a required path does not exist, use -1 for that entry.

Function Description

Complete the function shortestPathWithWaypoint in the editor below.

shortestPathWithWaypoint has the following parameters:

  1. int n: the number of nodes
  2. int[][] edges: undirected weighted edges [u, v, w]
  3. int start: the starting node
  4. int target: the destination node
  5. int waypoint: the node that the constrained path must visit

Returns

int[]: a length-2 array [bestDistance, bestDistanceViaWaypoint].

Examples
01 · Example 1
n = 5
edges = [[0, 1, 2], [1, 2, 3], [0, 3, 10], [2, 4, 1], [3, 4, 2], [1, 3, 2]]
start = 0
target = 4
waypoint = 1
return = [6, 6]

The shortest path from 0 to 4 is 0 -> 1 -> 2 -> 4 with total cost 6. That path already passes through the mandatory waypoint 1, so both answers are 6.

02 · Example 2
n = 4
edges = [[0, 1, 1], [1, 3, 1], [0, 2, 1]]
start = 0
target = 3
waypoint = 2
return = [2, -1]

The unconstrained shortest path is 0 -> 1 -> 3 with cost 2. There is no path from 2 to 3, so no valid route can pass through the waypoint.

Constraints
  • 1 <= n <= 2 * 10^5
  • 0 <= edges.length <= 3 * 10^5
  • 0 <= w <= 10^9
  • All edge weights are non-negative.
  • If no path exists for a requested scenario, return -1 for that entry.
More Google problems
drafts saved locally
public int[] shortestPathWithWaypoint(int n, int[][] edges, int start, int target, int waypoint) {
    // write your code here
}
n5
edges[[0, 1, 2], [1, 2, 3], [0, 3, 10], [2, 4, 1], [3, 4, 2], [1, 3, 2]]
start0
target4
waypoint1
expected[6, 6]
sign in to submit