Waymo Software Engineer Onsite Coding Questions

At the end of August, I applied to many micro-enterprises, and then the HR contacted me saying that several hiring managers were interested. I followed up with the group that best matched my backgroun

LeetCode #871: Minimum Number of Refueling Stops. Difficulty: Hard. Topics: Array, Dynamic Programming, Greedy, Heap (Priority Queue). Asked at Waymo in the last 6 months.

LeetCode #1944: Number of Visible People in a Queue. Difficulty: Hard. Topics: Array, Stack, Monotonic Stack. Asked at Waymo in the last 6 months.

LeetCode #359: Logger Rate Limiter. Difficulty: Easy. Topics: Hash Table, Design, Data Stream. Asked at Waymo in the last 6 months.

LeetCode #528: Random Pick with Weight. Difficulty: Medium. Topics: Array, Math, Binary Search, Prefix Sum, Randomized. Asked at Waymo in the last 6 months.

## Problem A "good number" is a positive integer of exactly N digits (no leading zeros) whose digit sum equals a given target S. Count how many such numbers exist. ```python def count_good_numbers(n: int, s: int) -> int: # n: number of digits (1 <= n <= 15) # s: required digit sum (0 <= s <= 9*n) # returns: count of n-digit numbers with digit sum == s pass ``` **Example:** ``` count_good_numbers(2, 5) # Valid: 14, 23, 32, 41, 50 -> 5 count_good_numbers(1, 0) -> 0 # no leading-zero single digit ``` ## Follow-ups 1. What is the recurrence relation for a dynamic programming solution? What is the state? 2. How does the first-digit constraint (no leading zeros) change the DP boundary condition? 3. Can you extend this to count numbers where each digit appears at most once? 4. How would you enumerate (not just count) all good numbers in sorted order efficiently?

## Problem Count distinct phone numbers a knight can dial in N moves on a phone keypad, using dynamic programming over valid knight moves. ## Likely LeetCode equivalent LeetCode 935 - Knight Dialer. ## Tags dynamic_programming,math,recursion,swe

## Problem Given a bipartite graph where left nodes are workers and right nodes are tasks, and each edge means a worker can perform that task, find the maximum number of tasks that can be assigned (one task per worker, one worker per task). ```python def max_matching(n: int, m: int, edges: list[tuple[int,int]]) -> int: # n: number of workers (0..n-1) # m: number of tasks (0..m-1) # edges: list of (worker, task) indicating compatibility # returns: size of maximum matching pass def find_matching(n: int, m: int, edges: list[tuple[int,int]]) -> dict[int,int]: # returns: dict mapping worker -> assigned task (only matched workers) pass ``` **Example:** ``` edges = [(0,0),(0,1),(1,1),(2,2)] max_matching(3, 3, edges) -> 3 find_matching(3, 3, edges) -> {0: 0, 1: 1, 2: 2} ``` ## Follow-ups 1. Walk through the augmenting path algorithm. What is its time complexity? 2. How does Hopcroft-Karp improve on the naive augmenting path approach? 3. How would you model task scheduling with deadlines as a maximum matching problem? 4. When might a minimum vertex cover be more useful than maximum matching?

## Problem Find the minimum cost to connect all nodes in a graph, likely a minimum spanning tree problem. ## Likely LeetCode equivalent LC 1584 (Min Cost to Connect All Points) is closely related. ## Tags graph, greedy, minimum-spanning-tree

## Problem Populate each tree node's next pointer to point to the next right node on the same level. ## Likely LeetCode equivalent LC 116 (Populating Next Right Pointers in Each Node) or LC 117. ## Tags binary_tree, BFS, level-order

## Problem A rabbit colony starts with one breeding pair. Each month, every mature pair produces one new pair. However, to prevent inbreeding, a pair may not breed with any pair that shares a common ancestor within K generations. Compute the population (number of pairs) after M months. ```python def rabbit_population(months: int, k: int) -> int: # months: total simulation months # k: inbreeding constraint (pairs sharing ancestor within k gens cannot breed) # returns: total number of pairs alive at end of month M pass ``` **Example:** ``` rabbit_population(6, 0) -> 8 # standard Fibonacci (no constraint) rabbit_population(6, 1) -> ? # pairs can't breed with their own offspring ``` ## Follow-ups 1. Without the inbreeding constraint (k=0), what is the recurrence relation and why does it match Fibonacci? 2. How does the inbreeding constraint change the recurrence? 3. How would you represent the ancestry graph to efficiently check whether two pairs share a common ancestor within K generations? 4. At what value of K does the constraint have no further effect on population growth?

## Problem You are given a finite state machine (FSM) defined by a set of states, an alphabet, a transition table, a start state, and a set of accepting states. Given an input string, determine whether the FSM accepts it. Also implement a method that returns all states reachable from the start state. ```python class FSM: def __init__(self, states: set[str], alphabet: set[str], transitions: dict[tuple[str,str], str], # (state, symbol) -> state start: str, accepting: set[str]): ... def accepts(self, input_str: str) -> bool: ... def reachable_states(self) -> set[str]: ... ``` **Example:** ``` # FSM that accepts strings ending in 'b' transitions = {('q0','a'):'q0', ('q0','b'):'q1', ('q1','a'):'q0', ('q1','b'):'q1'} fsm = FSM({'q0','q1'}, {'a','b'}, transitions, 'q0', {'q1'}) fsm.accepts("aab") -> True fsm.accepts("aba") -> False ``` ## Follow-ups 1. How would you convert this DFA to an NFA that accepts the complement language? 2. How do you detect unreachable states and why is removing them useful? 3. How would you implement DFA minimization (merging equivalent states)? 4. What changes are needed to support epsilon transitions (NFA with epsilon)?

## Problem Fit words into lines of a given width, justifying text so words fill each row evenly. ## Likely LeetCode equivalent LC 68 (Text Justification) is closely related. ## Tags strings, greedy, simulation

## Problem Given an `m × n` grid, fill it completely with 4 tokens labeled `1, 2, 3, 4` such that: 1. Every cell is assigned exactly one token (no empty cells). 2. Each token must occupy the **same n

## Problem: Count Same-Color Squares in a Grid You are given a 2D grid `grid` of characters. Each cell contains an uppercase letter (e.g., `A/B/C/D`) representing a color. The grid size is arbitrary

Given a set of points `points` on a 2D plane, where each point has integer coordinates `(x, y)`. Find the **maximum area** of an **axis-aligned** rectangle whose four vertices all appear in `points`.

## Problem: Minimum travel path for a pen-plotter to draw given strokes You are implementing a pen-plotter robot that moves a pen on paper to draw a figure. You are given **n strokes**, each stroke b

## Problem: Jump Game Variant (Reachability / Backtracking) Given an integer array `nums` of length `n`, you start at index `0`. - `nums[i]` is the **maximum** jump length from index `i` to the righ

You are given an event log. A player is in a **streak** as long as they keep performing the **same event type** repeatedly, and the time gap between consecutive actions is not greater than a threshold

Given an array `nums` of length `n` where each element is only `0`, `1`, or `2`. Return the minimum absolute index distance between any pair of indices `(i, j)` such that `nums[i] = 1` and `nums[j] =