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.
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?