How should I practice Fastest Favorite City Through a Required Vertex?

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

Is Fastest Favorite City Through a Required Vertex associated with Google?

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

Fastest Favorite City Through a Required Vertex

Google● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

An undirected weighted graph has roads [u,v,time] with positive travel times. Return the favorite city reachable in minimum total time from source.

If required is nonnegative, the route must visit that vertex; otherwise there is no required vertex. Break equal-time ties by smaller city ID. Return -1 if no favorite is reachable.

Function

fastestFavoriteCity(n: int, roads: int[][], favorites: int[], source: int, required: int) → int

Examples

Example 1

n = 5roads = [[0,1,2],[1,2,2],[0,3,10],[2,4,1]]favorites = [3,4]source = 0required = -1return = 4

Favorite 4 is reached in five units, faster than city 3.

Example 2

n = 5roads = [[0,1,1],[1,2,1],[0,3,1],[3,4,1],[2,4,10]]favorites = [2,4]source = 0required = 3return = 4

Requiring city 3 makes favorite 4 the best.

Example 3

n = 3roads = [[0,1,2]]favorites = [2]source = 0required = -1return = -1

The only favorite is unreachable.

Constraints

1 <= n <= 100000.
0 <= roads.length <= 200000.
Travel times are positive.