Minimum Travel Time with Flashing Traffic Lights
Updated
Problem statement
You are given a simple undirected graph with vertices numbered from 0 through n-1. Each edge [u,v,w] takes w time units to travel along in either direction.
The traffic light at vertex u flashes green only at the instants 0, periods[u], 2*periods[u], .... You may leave that vertex only at one of those times. If you arrive between flashes, wait for the next flash before taking another edge. A flash lasts for a single instant, not a period of time.
Start at source at time zero. Return the earliest arrival time at target, or -1 if you cannot reach it. You do not need to wait for a green light after arriving at the destination. For this exercise, assume all traversal times and periods are positive integers and return the answer as a 64-bit integer.
Function
minimumTravelTime(n: int, edges: int[][], periods: int[], source: int, target: int) → longExamples
Example 1
n = 3edges = [[0,1,2],[1,2,4]]periods = [2,3,4]source = 0target = 2return = 7Leave vertex 0 at time 0 and reach vertex 1 at time 2. Its next flash is time 3, so the final edge arrives at time 7. The destination's period causes no extra wait.
Example 2
n = 4edges = [[0,1,2],[1,3,2],[0,2,3],[2,3,1]]periods = [1,100,1,1]source = 0target = 3return = 4The route through 2 arrives at time 4. Going through 1 would wait until time 100 and arrive at 102.
Constraints
- For this exercise, assume
1 <= n <= 1000and at most 5000 edges. - The graph has no self-loops or parallel undirected edges, and may be disconnected.
- Every edge weight and vertex period is from 1 through
10^9. periods.length == nand both requested vertices belong to the graph.
More PeopleStrong interview questions
- Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
- Unique Paths Through a GridOA · Seen Mar 2026
- Aggressive CowsOA · Seen Oct 2021
- Shortest Path in an Unweighted GraphOA · Seen Oct 2021
- Total Set Bits from 1 to NOA · Seen Oct 2021
- Swap Two Array ElementsOA · Seen Sep 2021
- Permutation in a StringOA · Seen Aug 2021
- Rat in a Maze: All Simple PathsOA · Seen Aug 2021
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
Similar questions at other companies
- Minimum Stress PathWalmart · OAWalmart interview questions
- Dijkstra Shortest Paths in a Weighted Undirected GraphVisa · OAVisa interview questions
- Minimize Path ValuePalantir · OAPalantir interview questions
- Minimize Path ValueSalesforce · OASalesforce interview questions
- Cookie Monster Minimum Arrival TimeIntuit · OAIntuit interview questions
- Minimum Wizard Referral CostAirbnb · OAAirbnb interview questions
- Fuel Route with Fewest Station VisitsGoogle · ONSITE INTERVIEWGoogle interview questions
- Dynamic Broadcast TimesNetflix · PHONE SCREENNetflix interview questions
- Minimum Path Cost with Edge DiscountsSkyscanner · ONSITE INTERVIEWSkyscanner interview questions
- Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW