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

In `grid`, 0 is a road, 1 is an obstacle, and 2 is a traffic light. Start at time 0 at `start` and move up, down, left, or right, taking one time unit per move. You may wait at the current cell. Every light permits entry only at times 0, t, 2t, and so on. Starting on a light requires no wait. Return the earliest time you can reach `destination` or −1 if it is unreachable or either endpoint is blocked. Both coordinates use zero-based `[row, column]` pairs.

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

  1. An intermediate light can make a short path take more time than a longer path.

Earliest Arrival in a Traffic-Light Grid

hardWaymoMachine Learning Engineer

In grid, 0 is a road, 1 is an obstacle, and 2 is a traffic light. Start at time 0 at start and move up, down, left, or right, taking one time unit per move. You may wait at the current cell. Every light permits entry only at times 0, t, 2t, and so on. Starting on a light requires no wait.

Return the earliest time you can reach destination or −1 if it is unreachable or either endpoint is blocked. Both coordinates use zero-based [row, column] pairs.

Examples

Example 1
Input
([[0, 2, 0]], [0, 0], [0, 2], 5)
Output
6
Notes
Enter the middle cell at time 5, then take one more step.
Example 2
Input
([[0, 2, 0], [0, 0, 0]], [0, 0], [0, 2], 10)
Output
4
Notes
A four-step detour beats waiting for the direct light.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def minimum_traffic_grid_travel_time(grid: list[list[int]], start: list[int], destination: list[int], t: int) -> int:
Sample call
minimum_traffic_grid_travel_time([[0, 2, 0]], [0, 0], [0, 2], 5)
Language
Case 1
Input
([[0, 2, 0]], [0, 0], [0, 2], 5)
Expected
6
Case 2
Input
([[0, 2, 0], [0, 0, 0]], [0, 0], [0, 2], 10)
Expected
4

Browse More Questions

Show the approach

Approach

Use Dijkstra’s algorithm with earliest arrival times. At time u, entering an ordinary neighbor would arrive at u+1. For a light, round u+1 up to the next multiple of t. These arrival functions never decrease as u increases. Waiting also lets an earlier arrival imitate any later departure, so keeping just the earliest arrival per cell is sufficient.

Process the smallest unsettled time first and update incident moves. When the destination is removed from the heap with its current best time, no unprocessed route can improve it. Routes past the guaranteed maximum answer can be discarded because their times cannot decrease later.

Time complexity:
O(RC log(RC)) for R rows and C columns.
Space complexity:
O(RC) auxiliary space.