DS&A in Driving Scenarios

Waymo is an Alphabet company, so the coding bar is Google-grade: language-agnostic data structures and algorithms in the medium-to-hard range, solved live. What makes a round feel like Waymo rather than a generic Google loop is the costume. The prompt is rarely an abstract puzzle. It is a grid of city blocks with an obstacle in it, a collision between two objects you reason about before you type, a fleet of cars reporting positions over time. The structure underneath is a breadth-first search, an interval sweep, a hashmap. The self-driving scene is narrative. This lesson teaches the one skill that costume demands, the translation from story to structure, and then works three problems that live entirely inside it.

The Waymo angle

The autonomous-vehicle flavor front-loads a translation step, and the round measures that translation. Candidates commonly psych themselves out expecting Kalman filters or sensor-fusion math in the coding round. Reported rounds show standard DS&A in a driving suit instead. A grid becomes a map, a shortest path becomes a route, and a graph becomes a road network or an org chart. A stream of pings becomes a hashmap keyed by car. You have to hear the story and extract the structure before you write a line. Once the structure is named, the solution is the one you already know. Prepare the fundamentals cold, then rehearse the reduction, rather than chasing robotics theory the coding loop does not test.

The translation drill

Every driving-flavored prompt yields to the same three-move drill. The discipline is doing the moves in order instead of jumping to code from the surface story. First, restate the scene in your own words until the physics or the map stops being the point. Second, name the underlying structure out loud: a grid you flood-fill, a set of intervals you sweep, or a keyed lookup holding the latest value. Third, and only third, write the ordinary code for that structure. The failure mode is skipping straight to move three. You hear the word collision and model velocity vectors when the problem wanted a comparison and a direction. Or you reach for a weighted shortest path when a plain breadth-first search on an unweighted grid was all it needed.

The Byteboard screen and the live loop both weight this. Byteboard is a project-style assessment: you read a scenario, write code against it, and explain your choices in short-answer boxes. A clear working solution you can justify beats a clever fragment. The live domain-flavored round escalates constraints mid-problem, and the interviewer watches how your model bends. Build something that runs, narrate the reduction as you go, then be ready to change it. Each of the three problems below is the standard structure, worked in full, with the driving skin kept honest and cosmetic.

Occupancy grid: reachable cells before the hazard

The most Waymo of the standard shapes is the occupancy grid. A cell is either drivable or blocked, the vehicle sits on one square, and the question is some flavor of how far it can get. Reading how many cells are reachable inside a fixed number of moves is a breadth-first search with a step budget, nothing more. The driving frame, a hazard closing in so the vehicle has only so many moves to plan around, is the costume over an ordinary level-order flood fill.

1

Occupancy Grid: Reachable Cells in a Step Budget

MediumFrequently asked

Problem

You are given an occupancy grid grid, a 2D array where 0 is a drivable cell and 1 is an obstacle. The vehicle starts at start = [row, col]. It moves one cell at a time up, down, left, or right, never onto an obstacle and never off the grid. Given an integer budget, return the number of distinct cells the vehicle can occupy using at most budget moves, counting the starting cell itself.

If the start cell is an obstacle, the vehicle cannot be there, so the answer is 0.

Input: grid = [[0,0,1],[0,1,0],[0,0,0]], start = [0,0], budget = 3

Output: 5

From (0,0) the reachable cells within 3 moves are (0,0), (0,1), (1,0), (2,0), and (2,1). The cell (2,2) sits 4 moves away, past the budget.

Input: grid = [[0,0],[0,0]], start = [0,0], budget = 1

Output: 3

One move reaches (0,1) and (1,0); together with the start that is 3 cells.

How this uses the pattern

Breadth-first search carries distance outward one ring at a time. Push the start with distance 0, and when you pop a cell whose distance already equals the budget, stop expanding from it. Every cell you mark visited within the budget counts once.

Occupancy Grid: Reachable Cells in a Step Budget

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[[0,0,1],[0,1,0],[0,0,0]],[0,0],3]Expected: 5

Input: [[[0,0,1],[0,1,0],[0,0,0]],[0,0],0]Expected: 1

Input: [[[0,0,1],[0,1,0],[0,0,0]],[0,0],10]Expected: 7

Input: [[[0,0,1],[0,1,0],[0,0,0]],[0,2],3]Expected: 0

Input: [[[0]],[0,0],5]Expected: 1

Input: [[[0,0],[0,0]],[0,0],1]Expected: 3

Need a hint? (3 available)

The Waymo angle

The occupancy grid is the cleanest example of Waymo painting its domain onto a standard round. Reported grid problems include placing an object on the square that minimizes total travel to a set of machines. That is the same breadth-first machinery run from several sources. The interviewer watches whether you reach for a plain level-order search on an unweighted grid instead of a weighted shortest path. They also watch whether you mark a cell visited when you enqueue it rather than when you dequeue it, so no cell is counted twice.

Take it further

Now the hazard spreads too. Suppose one or more cells start on fire and the fire also expands one cell per move. A cell is only safe to occupy if the vehicle can reach it strictly before the fire does. That is a multi-source breadth-first search for the fire arrival times, run first, followed by the same vehicle search that rejects any cell it cannot reach earlier. Same structure, two passes.

Show solution & walkthrough

Detection windows: merging overlapping intervals

The perception stack fires a detection every time a sensor believes an object is present, each detection covering a small window of time. Several sensors watching the same object produce windows that touch and overlap, and the consumer wants one consolidated span per real detection rather than a pile of fragments. Stripped of the sensor story, that is Merge Intervals: sort by start, sweep once, and fuse anything that touches. The costume is the detection stream; the structure is the interval sweep.

2

Detection Windows: Merge Overlapping Intervals

MediumSometimes asked

Problem

You are given a list windows where windows[i] = [start, end] is one time window during which a sensor reported a detection. Two windows belong to the same real detection when they overlap or merely touch, so [1,3] and [2,6] fuse into [1,6], and [1,4] and [4,5] fuse into [1,5] because they meet at the endpoint.

Merge every group of connected windows and return the consolidated windows sorted by start time.

Input: windows = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

[1,3] and [2,6] overlap into [1,6]. The other two touch nothing and pass through.

Input: windows = [[1,4],[4,5]]

Output: [[1,5]]

They meet at 4, and touching counts as connected, so they fuse into [1,5].

How this uses the pattern

Sort by start time, then sweep left to right holding the last merged window open. For each next window, if its start is at or before the held end, extend the held end to the larger of the two. Otherwise a real gap sits between them, so start a fresh window.

Detection Windows: Merge Overlapping Intervals

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[[1,3],[2,6],[8,10],[15,18]]]Expected: [[1,6],[8,10],[15,18]]

Input: [[[1,4],[4,5]]]Expected: [[1,5]]

Input: [[]]Expected: []

Input: [[[1,4]]]Expected: [[1,4]]

Input: [[[1,4],[2,3]]]Expected: [[1,4]]

Input: [[[5,6],[1,3],[2,4]]]Expected: [[1,4],[5,6]]

Need a hint? (3 available)

The Waymo angle

Merging overlapping windows is the interval sweep in a self-driving suit, and the endpoint rule decides it. A real detection can span two sensor windows that only touch at an instant, so touching must count as connected. The overlap test is start at or before end, written with a less-than-or-equal. A strict less-than is the quiet bug that leaves two touching windows as separate detections, and the round probes exactly that edge.

Take it further

Report the busiest instant instead of the merged spans. If you want the maximum number of sensors that ever detect the object at the same moment, do not merge at all. Split each window into a plus-one start event and a minus-one end event, sort the events, and sweep a running counter, tracking its peak. That is the sweep-line count, a close cousin of the merge that answers a different question.

Show solution & walkthrough

The fleet tracker: latest position per car

The third shape is a stream. Cars in the fleet report their positions over time, the updates arrive in chronological order, and a monitor wants each car's most recent position. This is a documented Waymo round: track car positions, return the latest per car, then have the interviewer bound the history and watch you adapt. The base case is a hashmap keyed by car, where a later ping simply overwrites the earlier one. No sorting of the stream, no scan back through history, just a keyed lookup that always holds the freshest value.

3

Fleet Tracker: Latest Position Per Car

EasyFrequently asked

Problem

You are given a list updates in chronological order, where updates[i] = [car_id, x, y] records that vehicle car_id reported position (x, y). A later update for the same car supersedes its earlier ones.

Return each car's most recent position as a list of [car_id, x, y], sorted by car_id ascending.

Input: updates = [[1,0,0],[2,5,5],[1,1,1],[3,2,2],[2,6,6]]

Output: [[1,1,1],[2,6,6],[3,2,2]]

Car 1 last reported (1,1), car 2 last reported (6,6), car 3 reported (2,2). Output is ordered by car id.

Input: updates = [[5,1,1],[5,2,2],[5,3,3]]

Output: [[5,3,3]]

Only car 5 appears; its last report (3,3) wins.

How this uses the pattern

Walk the updates once, storing each car id to its current position in a hashmap. Because the stream is chronological, a plain overwrite keeps the latest. At the end, read the map out in sorted key order.

Fleet Tracker: Latest Position Per Car

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[[1,0,0],[2,5,5],[1,1,1],[3,2,2],[2,6,6]]]Expected: [[1,1,1],[2,6,6],[3,2,2]]

Input: [[]]Expected: []

Input: [[[7,3,4]]]Expected: [[7,3,4]]

Input: [[[2,0,0],[1,9,9],[2,1,1]]]Expected: [[1,9,9],[2,1,1]]

Input: [[[5,1,1],[5,2,2],[5,3,3]]]Expected: [[5,3,3]]

Need a hint? (3 available)

The Waymo angle

The fleet tracker is the hashmap in a Waymo costume, and it is a reported round because of what comes after the base case. Once the latest position works, the interviewer bounds the history: keep only the last k positions per car. Each map value turns from a single point into a capped sequence, which forces a list-versus-deque tradeoff. The interviewer is watching your model bend under a moving constraint. Build the simplest correct version first, and keep it clean enough to extend.

Take it further

Bound the history to the last k positions per car. Change each map value from a single position to a fixed-length deque of the most recent k. On each update, append and drop the oldest once the deque is full, so the memory per car stays constant. A deque gives O(1) at both ends where a plain list would pay O(k) to pop from the front. That is the escalation this problem is known for.

Show solution & walkthrough

What is costume, and what is not

The three problems above share one design: a scene from the road wrapped around a structure from week one of a data-structures course. Name that shared design and the domain-flavored round loses its bite. Be just as clear about where the costume stops.

Common questions