Find Minimum Grid Travel Time with Periodic Traffic Lights

Quick Overview

Find earliest travel through a grid with periodic traffic lights using Dijkstra, explicit green-time assumptions, waiting calculations, and FIFO reasoning.

Find Minimum Grid Travel Time with Periodic Traffic Lights

Company: Waymo

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

An m by n grid contains free roads (0), obstacles (1), and traffic lights (2). Starting at time zero, move in four orthogonal directions; each move takes one time unit. A traffic-light cell can be entered only when green. Return the earliest arrival time at the destination, or -1 if unreachable. ### Constraints & Assumptions The source says lights become green every T units but omits green duration and phase. For this practice version, all lights permit entry exactly at times 0, T, 2T, and so on, where T is a positive integer. You may wait at the current cell; a light at the starting cell imposes no extra initial wait. Confirm these assumptions before adapting to an alternating green/red-cycle variant. ### Clarifying Questions to Ask - Is green an instant or an interval, and are all lights synchronized? - Is waiting allowed before entering the next cell? ```hint Arrival cost depends on current time Two adjacent moves can have different effective costs because one may include waiting for a light. ``` ### What a Strong Answer Covers - Time-dependent edge relaxation and rounding entry time to the next permitted light time. - Dijkstra's algorithm rather than unweighted BFS. - The earliest-arrival/FIFO property, blocked endpoints, and unreachable destinations. ### Follow-up Questions - How would a green interval of length G within each cycle change the waiting formula? - Why is it safe to discard a later arrival at a cell under this waiting policy?

Overview: Find earliest travel through a grid with periodic traffic lights using Dijkstra, explicit green-time assumptions, waiting calculations, and FIFO reasoning.

Read the full Waymo Machine Learning Engineer interview experience this question came from

Waymo logo
Waymo
Apr 20, 2026
hardMachine Learning EngineerTechnical ScreenCoding & Algorithms
0
0

An m by n grid contains free roads (0), obstacles (1), and traffic lights (2). Starting at time zero, move in four orthogonal directions; each move takes one time unit. A traffic-light cell can be entered only when green. Return the earliest arrival time at the destination, or -1 if unreachable.

Constraints & Assumptions

The source says lights become green every T units but omits green duration and phase. For this practice version, all lights permit entry exactly at times 0, T, 2T, and so on, where T is a positive integer. You may wait at the current cell; a light at the starting cell imposes no extra initial wait. Confirm these assumptions before adapting to an alternating green/red-cycle variant.

Clarifying Questions to Ask Guidance

  • Is green an instant or an interval, and are all lights synchronized?
  • Is waiting allowed before entering the next cell?

What a Strong Answer Covers Guidance

  • Time-dependent edge relaxation and rounding entry time to the next permitted light time.
  • Dijkstra's algorithm rather than unweighted BFS.
  • The earliest-arrival/FIFO property, blocked endpoints, and unreachable destinations.

Follow-up Questions Guidance

  • How would a green interval of length G within each cycle change the waiting formula?
  • Why is it safe to discard a later arrival at a cell under this waiting policy?