In April I started applying broadly, and then a recruiter reached out and scheduled a 45-minute technical screen.
From reading other interview reports, I got the impression Waymo likes graph questions in its screens. I got a graph question too.
I was not especially comfortable with graph problems. I used BFS and struggled to write some of it. When I ran it, I was asked to try two tests, but both produced the same output. Unsurprisingly, I was rejected. Here is the question:
Shortest Travel Time in a Grid with Traffic Lights
You are given an m × n 2D grid representing a road network. Each cell represents a location and can contain one of three values:
0 (Free Road): The car can pass through this cell without any restrictions.
1 (Obstacle): The car cannot pass through this cell.
2 (Traffic Light): The car can only pass through this cell when the traffic light is green. The traffic light turns green periodically, every T units of time.
You are also given a starting position (startRow, startCol) and a destination (endRow, endCol).
The car can move in four directions: up, down, left, and right. Each move to an adjacent cell takes one unit of time.
If the car encounters a red traffic light, it must wait until the light turns green before proceeding.
Your task: Find the minimum time required to travel from the starting position to the destination. If the destination is unreachable, return -1.
Job hunting is not easy. I hope everyone lands something soon!
Discussion
Loading comments…