FastPrepShortest Travel Time in a Grid with Traffic Lights
Problems/Shortest Travel Time in a Grid with Traffic Lights

Shortest Travel Time in a Grid with Traffic Lights

Waymo logoWaymo● MediumNEW GRADPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Waymo new grad machine learning engineer phone screen. The task was to find the fastest drive across a grid of free roads, obstacles and traffic lights, where the car has to wait at a red light, or return -1 when the end cannot be reached.

The report says each light comes back to green on a cycle of length T, but not how long it stays green. Here, a light is green only at the times T, 2T, 3T and so on, and the car may move into a light cell only at one of those times. It can leave a light cell at any time. The report gives no limits, so we use grids up to 100 x 100 and T up to 1000.

Our version is about 85% the same as the reported question.

You are given an m x n grid grid that represents a road network. Each cell holds one of three values:

  • 0 (free road): the car can drive into this cell at any time.
  • 1 (obstacle): the car can never enter this cell.
  • 2 (traffic light): the car can enter this cell only while its light is green. Every light is green exactly at the times T, 2T, 3T, and so on, and red at every other time.

The car starts at (startRow, startCol) at time 0 and wants to reach (endRow, endCol). In one move the car goes up, down, left, or right to a cell inside the grid, and each move takes 1 unit of time. A move into a traffic-light cell is allowed only if it ends at a green time. When the light ahead is red, the car waits in its current cell until it can make that move. The car may wait in its current cell for any whole number of time units, and leaving a traffic-light cell does not need a green light.

Return the minimum time for the car to reach the destination. If the destination is unreachable, return -1.

Function

shortestTravelTime(grid: int[][], T: int, startRow: int, startCol: int, endRow: int, endCol: int) → int

Examples

Example 1

grid = [[0,2,0],[0,1,0],[0,0,0]]T = 3startRow = 0startCol = 0endRow = 0endCol = 2return = 4
grid
012002010102000
  • The light at (0, 1) is green at times 3, 6, 9 and so on.
  • Through the light: wait at (0, 0) until time 2, enter the light at time 3, then reach (0, 2) at time 4.
  • Around the obstacle: (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2) takes 6 moves.
  • The fastest time is 4.

Example 2

grid = [[0,1],[1,0]]T = 2startRow = 0startCol = 0endRow = 1endCol = 1return = -1
grid
01001110
  • Both neighbors of (0, 0) are obstacles, so the car can never leave its start.
  • The destination is unreachable, so the answer is -1.

Example 3

grid = [[0,0,0,2]]T = 5startRow = 0startCol = 0endRow = 0endCol = 3return = 5
grid
012300002
  • The car reaches (0, 2) at time 2.
  • The destination (0, 3) is a light, and it is green only at times 5, 10 and so on.
  • The car waits at (0, 2) until time 4 and enters the destination at time 5.

Constraints

  • m == grid.length and n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] is 0, 1, or 2.
  • 1 <= T <= 1000
  • 0 <= startRow, endRow < m
  • 0 <= startCol, endCol < n
  • grid[startRow][startCol] != 1 and grid[endRow][endCol] != 1

More Waymo Phone Screen questions

  • Fixed-Order Task Run Time With CooldownPHONE SCREEN · Seen Oct 2026
  • Reorderable Task Scheduler With CooldownPHONE SCREEN · Seen Oct 2026
  • Island Area and Water BoundaryPHONE SCREEN · Seen Sep 2026
  • Vehicle Maintenance Event ReadinessPHONE SCREEN · Seen Sep 2026
  • Obstacle-Aware Return to OriginPHONE SCREEN · Seen Sep 2026
  • Shortest Paths to Multiple TargetsPHONE SCREEN · Seen Sep 2026
  • Deterministic Depth-First Graph TraversalPHONE SCREEN · Seen Sep 2026
  • Shortest Distance from All BuildingsPHONE SCREEN · Seen Sep 2026
  • Fixed-Range Frequency CountPHONE SCREEN · Seen Aug 2026
  • Insert an Employee into an Organization HierarchyPHONE SCREEN · Seen Aug 2026

Similar questions at other companies

  • Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Shortest Path with Directional Move CostsThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
  • Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
  • Maximum-Clearance Path From a PointGoogle · PHONE SCREENGoogle interview questions
  • Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
  • Minimum-Cost Path Through a Weighted GridVisa · OAVisa interview questions
  • Grid ExplorationIMC Trading · OAIMC Trading interview questions
  • Cookie Monster Minimum Arrival TimeIntuit · OAIntuit interview questions
  • Drone Delivery with Battery Swap StationsCisco · OACisco interview questions

Interview reports that mention this question

  • Waymo New Grad MLE Phone Screen: Traffic Lights: 1 Experience
All Waymo interview questionsSee Waymo hiring insights
Saved
class Solution {
    public int shortestTravelTime(int[][] grid, int T, int startRow, int startCol, int endRow, int endCol) {
        // Write your code here.
    }
}
Checking account…