Find Minimum Grid Travel Time with Periodic Traffic Lights
Company: Waymo
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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
Constraints
- The nonempty grid is rectangular and contains at most 2^31 − 1 cells. Both coordinate pairs are in bounds.
- The period t is an integer from 1 through 2^53 − 1 inclusive.
- Any reachable destination has earliest arrival in the range 0 through 2^53 − 1. Other arrivals may exceed this range.
Examples
Input: ([[0, 2, 0]], [0, 0], [0, 2], 5)
Expected Output: 6
Explanation: Enter the middle cell at time 5, then take one more step.
Input: ([[0, 2, 0], [0, 0, 0]], [0, 0], [0, 2], 10)
Expected Output: 4
Explanation: A four-step detour beats waiting for the direct light.
Hints
- An intermediate light can make a short path take more time than a longer path.