How should I practice Shortest Path Through a Required 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 Through a Required 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.

Shortest Path Through a Required Waypoint

Google● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Given a directed weighted graph, find the shortest distance from start to target, and the shortest distance for a walk that visits waypoint on its way from start to target.

Vertices are labeled 0 through n-1. Each edge [from,to,weight] can be traversed in its given direction and has nonnegative weight. Multiple edges and self-loops are allowed. A walk may repeat vertices or edges, and waypoint may equal an endpoint.

Return [direct, via]. Set a result to -1 when that route does not exist. A zero-length walk from a vertex to itself has distance 0.

Function

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

Examples

Example 1

n = 4edges = [[0,1,2],[1,3,4],[0,2,1],[2,3,10],[1,2,1]]start = 0target = 3waypoint = 2return = [6,11]

The shortest direct route has cost 6. Passing through vertex 2 costs 11 via the direct edge to 2.

Example 2

n = 3edges = [[0,1,5]]start = 0target = 2waypoint = 1return = [-1,-1]

Vertex 2 is unreachable, even after passing through 1.

Example 3

n = 2edges = [[0,1,7]]start = 0target = 1waypoint = 0return = [7,7]

When the waypoint is the start, the two shortest distances are equal.

Constraints

1 <= n <= 1000.
0 <= edges.length <= 5000.
Each edge is [from,to,weight] with valid vertices and 0 <= weight <= 10000.
start, target, and waypoint are valid vertices.