FastPrepMinimum Travel Time with Flashing Traffic Lights
Problems/Minimum Travel Time with Flashing Traffic Lights

Minimum Travel Time with Flashing Traffic Lights

PeopleStrong logoPeopleStrong● HardFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a PeopleStrong online assessment. The task uses green flashes at whole-number multiples of each vertex's period, and you wait until the next flash to leave. This keeps that rule, instead of alternating red and green intervals. We chose the function interface, the number limits, and a 64-bit output. Our version is about 95% the same as the reported question.

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) → long

Examples

Example 1

n = 3edges = [[0,1,2],[1,2,4]]periods = [2,3,4]source = 0target = 2return = 7

Leave 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 = 4

The 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 <= 1000 and 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 == n and 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

Interview reports that mention this question

  • PeopleStrong SDE OA and Interview Questions: 12 Experiences
All PeopleStrong interview questionsSee PeopleStrong hiring insights
Saved
class Solution {
    public long minimumTravelTime(int n, int[][] edges, int[] periods, int source, int target) {
        // Write your solution here.
    }
}
Checking account…