How should I practice Shortest Path with Mandatory Waypoint?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Shortest Path with Mandatory Waypoint associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Shortest Path with Mandatory Waypoint

Learn this problem

● Medium

GoogleFULLTIMEONSITE INTERVIEW

See Google hiring insights

Problem statement

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

Compute two values:

the length of the shortest path from start to target
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

shortestPathWithWaypoint(n: int, edges: int[][], start: int, target: int, waypoint: int) → int[]

Complete the function shortestPathWithWaypoint in the editor below.

shortestPathWithWaypoint has the following parameters:

int n: the number of nodes
int[][] edges: directed weighted edges [u, v, w]
int start: the starting node
int target: the destination node
int waypoint: the node that the constrained path must visit

Returns

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

Examples

Example 1

n = 5edges = [[0, 1, 2], [1, 2, 3], [0, 3, 10], [2, 4, 1], [3, 4, 2], [1, 3, 2]]start = 0target = 4waypoint = 1return = [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.

Example 2

n = 4edges = [[0, 1, 1], [1, 3, 1], [0, 2, 1]]start = 0target = 3waypoint = 2return = [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.