Waymo Software Engineer Phone Screen Questions

Recently did an SWE coding phone screen. Between the 5 min intro, and 7 min questions at the end, I only have like 30ish mins for two questions. I coded the first one within like 20 mins, but that onl

They asked very detailed questions about my resume, including some behavioral questions, such as how I recovered from a failed project, a project I'm particularly proud of, and how I handled conflicts

## Problem Simulate a ball dropping through a grid of deflectors, determining the column where it exits at the bottom. ## Likely LeetCode equivalent LeetCode 1706 - Where Will the Ball Fall. ## Tags matrix,simulation,arrays,swe

## Problem Implement a board-based game or simulation on a 2D grid, tracking state of cells and computing outcomes based on rules. ## Likely LeetCode equivalent LeetCode 289 - Game of Life. ## Tags matrix,simulation,arrays,swe

## Problem You are given a trip log as a list of `(timestamp, odometer_reading)` tuples recorded at irregular intervals. Compute the average speed of the car, excluding periods when the car was stationary (speed = 0). ```python from typing import List, Tuple def average_moving_speed(log: List[Tuple[float, float]]) -> float: # log: list of (time_seconds, distance_km) sorted by time # returns: average speed in km/h over moving segments only pass ``` **Example:** ``` log = [(0, 0), (3600, 60), (7200, 60), (10800, 120)] # Segment 0->1: 60 km/h (moving) # Segment 1->2: 0 km/h (stopped) # Segment 2->3: 60 km/h (moving) average_moving_speed(log) -> 60.0 ``` ## Follow-ups 1. What is the threshold to distinguish a brief slowdown from a genuine stop? 2. How would you identify and report distinct stop locations along the route? 3. If timestamps have GPS drift (jitter of +/-2 s), how does that affect speed calculation? 4. How would you extend this to compute fuel efficiency (L/100 km) if fuel data is added?

## Problem Design a car leasing system where customers can reserve vehicles for date ranges. The system must prevent double-booking, compute total charges, and handle early returns with partial refunds. ```python from datetime import date class CarLeasingSystem: def add_car(self, car_id: str, daily_rate: float) -> None: ... def reserve(self, car_id: str, customer: str, start: date, end: date) -> str: # returns reservation_id ... def cancel(self, reservation_id: str) -> float: # returns refund amount ... def available(self, start: date, end: date) -> list[str]: # car_ids ... ``` **Example:** ``` add_car("C1", daily_rate=50.0) reserve("C1", "alice", date(2024,6,1), date(2024,6,7)) -> "RES-001" reserve("C1", "bob", date(2024,6,5), date(2024,6,9)) -> raises ConflictError available(date(2024,6,8), date(2024,6,10)) -> ["C1"] ``` ## Follow-ups 1. How do you efficiently query available cars for a date range when there are 10,000 vehicles? 2. What data structure supports overlap detection in O(log n)? 3. How would you add a loyalty discount for customers with more than 10 past reservations? 4. How would you handle time zones if cars are rented across multiple countries?

## Problem N cars start at position 0 on a one-lane road and drive at constant speeds. A "passing event" occurs the instant a faster car catches a slower car ahead of it. Count the total number of passing events. ```python def count_passes(speeds: list[int]) -> int: # speeds[i] = speed of car i; cars start at positions 0..N-1 # car i starts ahead of car i+1 (i.e., position i) # returns total number of times a car overtakes the car directly ahead pass ``` **Example:** ``` speeds = [3, 4, 2, 5] # Car 1 (speed 4) passes Car 0 (speed 3) # Car 3 (speed 5) passes Car 2 (speed 2), then Car 1, then Car 0 count_passes([3, 4, 2, 5]) -> 4 ``` ## Follow-ups 1. Is this equivalent to counting inversions? If so, can you solve it in O(n log n) using merge sort? 2. What changes if the road has finite length and cars exit when they reach the end? 3. How would you extend this to return the exact times each passing occurs? 4. What if cars start at distinct initial positions instead of 0, 1, 2, ..., N-1?

## Problem Given a list of bus stops with (latitude, longitude) coordinates and a query point, return the ID of the nearest bus stop. Optimize for repeated queries over the same stop dataset. ```python from dataclasses import dataclass @dataclass class Stop: id: str lat: float lon: float class BusStopFinder: def __init__(self, stops: list[Stop]): ... def nearest(self, lat: float, lon: float) -> str: ... ``` **Example:** ``` stops = [Stop("A", 40.7128, -74.0060), Stop("B", 40.7580, -73.9855)] finder = BusStopFinder(stops) finder.nearest(40.730, -74.000) -> "A" ``` Use Euclidean distance as an approximation (haversine not required). ## Follow-ups 1. What data structure would you use to answer nearest-neighbor queries sub-linearly? Walk through a k-d tree insertion. 2. When does Euclidean distance fail for geographic coordinates, and how does haversine fix it? 3. If stops are updated in real time (added/removed every few seconds), how do you keep the structure fresh? 4. How would you extend this to return the K nearest stops sorted by distance?

## Problem Consolidate or compress a sequence of values by merging consecutive identical or overlapping entries into a compact representation. ## Likely LeetCode equivalent LeetCode 56 - Merge Intervals. ## Tags arrays,sorting,two_pointers,swe

## Problem Determine if it is possible to finish all courses given prerequisite constraints, using topological sort to detect cycles. ## Likely LeetCode equivalent LeetCode 207 - Course Schedule. ## Tags graph,topological_sort,dfs,swe

## Problem Given a sequence of GPS waypoints representing a planned route, compute the total driving distance. Each consecutive pair of waypoints is connected by a road segment whose distance is provided in a distance matrix. ```python def total_distance( waypoints: list[str], dist: dict[tuple[str, str], float] ) -> float: # waypoints: ordered list of location IDs # dist: symmetric distance map between adjacent stops # returns: sum of segment distances # raises: ValueError if a required segment is missing pass ``` **Example:** ``` waypoints = ["A", "B", "C", "A"] dist = {("A","B"): 5.0, ("B","C"): 3.0, ("C","A"): 4.0} total_distance(waypoints, dist) -> 12.0 ``` ## Follow-ups 1. How would you find the shortest route visiting all waypoints exactly once (TSP)? What is the complexity? 2. If the route loops back to the start, how do you detect and handle it? 3. How would you incorporate real-time traffic data to adjust segment distances dynamically? 4. What changes if some segments are one-way (the distance matrix is asymmetric)?

## Problem Determine the winner of an election from a list of votes, finding the candidate with the most votes. ## Likely LeetCode equivalent LeetCode 169 - Majority Element. ## Tags hash_table,sorting,arrays,swe

## Problem Fillomino is a logic puzzle where you fill an N x M grid so that every cell belongs to a connected region of cells, and each region's size equals the number written in any of its cells. Given a partially filled grid, write a solver that completes it. ```python def solve_fillomino(grid: list[list[int]]) -> list[list[int]]: # 0 = empty cell; non-zero = given clue # Returns completed grid, or raises if no solution exists pass def is_valid(grid: list[list[int]]) -> bool: # Validates a completed grid against Fillomino rules pass ``` **Example (4x4):** ``` Input: Output: [3, 0, 0, 2] [3, 3, 3, 2] [0, 0, 0, 2] [4, 4, 4, 2] [0, 0, 4, 0] [1, 4, 4, 4] [0, 0, 0, 0] [5, 5, 5, 5] ``` ## Follow-ups 1. What pruning strategies reduce backtracking? (Describe constraint propagation.) 2. How do you detect that two regions of the same number would need to merge, which is illegal? 3. What is the worst-case complexity of your backtracking solution? 4. How would you generate a valid Fillomino puzzle with a unique solution?

## Problem Find a path between two nodes in a graph or grid, using BFS or DFS to determine existence or shortest path. ## Likely LeetCode equivalent LeetCode 797 - All Paths From Source to Target. ## Tags graph,bfs,dfs,swe

## Problem Design a system to track the occupancy of a multi-level parking garage. Cars enter and exit through a single shared gate; each floor has a fixed capacity. The system must report current occupancy per floor and total, and reject entry when the garage is full. ```python class GarageCounter: def __init__(self, floors: dict[int, int]): # floor_id -> capacity ... def enter(self, floor: int) -> bool: # True if admitted ... def exit(self, floor: int) -> None: ... def occupancy(self, floor: int = None) -> int: # None = total ... def available_spots(self) -> dict[int, int]: ... ``` **Example:** ``` g = GarageCounter({1: 2, 2: 3}) g.enter(1) -> True g.enter(1) -> True g.enter(1) -> False # floor 1 full g.exit(1) g.enter(1) -> True g.occupancy() -> 3 ``` ## Follow-ups 1. How would you make `enter` and `exit` thread-safe for concurrent access at a real gate? 2. How would you expose occupancy via a real-time WebSocket endpoint? 3. If sensors occasionally misfire (double-counting an exit), how do you detect and correct drift? 4. How would you add a reservation system that holds spots for a time window?

## Problem Traverse a graph using BFS or DFS, computing reachability, connected components, or ordering of nodes. ## Likely LeetCode equivalent LeetCode 200 - Number of Islands. ## Tags graph,bfs,dfs,swe

## Problem Count the number of '1' bits in an integer's binary representation (popcount). ## Likely LeetCode equivalent LeetCode 191 - Number of 1 Bits. ## Tags math,binary,bit_manipulation,swe

## Problem Perform operations on a matrix of integers such as rotation, transposition, or finding values meeting a condition. ## Likely LeetCode equivalent LeetCode 48 - Rotate Image. ## Tags matrix,arrays,math,swe

## Problem Given a list of integers and a target range [lo, hi], rescale each value to fit within that range. Values should be scaled proportionally. Handle edge cases: all identical values, negative inputs, and integer-only output. ```python def rescale(values: list[int], lo: int, hi: int) -> list[float]: # Maps min(values)->lo, max(values)->hi linearly # Returns rescaled values as floats pass def rescale_int(values: list[int], lo: int, hi: int) -> list[int]: # Same but rounds to nearest integer pass ``` **Example:** ``` rescale([10, 20, 30], 0, 100) -> [0.0, 50.0, 100.0] rescale([5, 5, 5], 0, 10) -> [5.0, 5.0, 5.0] # degenerate case rescale([-10, 0, 10], 0, 1) -> [0.0, 0.5, 1.0] ``` ## Follow-ups 1. When all values are equal, what value should the output contain? Justify your choice. 2. How does floating-point precision affect the rescaled output when the range is very large? 3. How would you implement a streaming version that updates the scale as new values arrive? 4. How would you extend this to support per-column rescaling on a 2D matrix?

## Problem Query or aggregate values over intervals, such as counting points within ranges or finding interval overlaps. ## Likely LeetCode equivalent LeetCode 57 - Insert Interval. ## Tags arrays,sorting,intervals,swe