Waymo·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Waymo SWE interview, coding round, one graph problem the whole session. Screen sharing was mandatory the entire time which added a weird layer of pressure I wasn't fully prepared for.

Questions Asked (1)

Given a list of (parent, child) edge pairs representing a graph, determine whether the graph forms a valid forest (i.e., one or more valid trees with no cycles and no disconnected anomalies). You also need to design your own test cases.

Algorithms & Data Structures

Author's notes

The test case design part tripped me up more than the actual algorithm.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the definition of a valid forest: each node has at most one parent, there are no cycles, and all nodes are connected within their respective trees. Use union-find to detect cycles and validate parent constraints, then verify that the number of edges equals the number of nodes minus the number of trees. Design test cases covering empty input, single node, multiple trees, cycles, multiple parents, and disconnected components.

Pro tip: Explicitly state your assumptions about input format (e.g., nodes are integers, edges are directed parent->child) and edge cases before coding. This shows thoroughness and prevents misunderstandings, especially in a safety-critical company like Waymo.

1. Clarify requirements and edge cases

Ask clarifying questions about input format, node labeling, and what constitutes a 'disconnected anomaly'. Define edge cases such as empty input, single node, self-loops, and duplicate edges.

2. Choose data structures and algorithm

Select union-find for cycle detection and parent tracking. Alternatively, use DFS with visited states, but union-find is more efficient for dynamic connectivity.

3. Implement validation logic

Iterate through edges: check that each child has only one parent, union parent and child, and detect cycles. After processing, ensure all nodes belong to a single tree per component and no extra edges.

4. Design comprehensive test cases

Create tests for: empty list, single node, valid single tree, valid forest (multiple trees), cycle, multiple parents, disconnected node, and self-loop. Include both positive and negative cases.

5. Analyze complexity and discuss trade-offs

State time and space complexity (O(N α(N)) with union-find). Discuss alternative approaches like DFS and their trade-offs in terms of simplicity and performance.

Key Points to Mention

Definition of a forest: a collection of trees where each node has at most one parent and no cycles exist.
Union-Find (Disjoint Set Union) with path compression and union by rank for efficient cycle detection.
Parent constraint: each child node must have exactly one parent (except roots).
Edge count validation: for a forest with N nodes and K trees, the number of edges must be N - K.
Handling disconnected components: each component must be a valid tree, and there should be no isolated nodes unless they are single-node trees.
Test case design: include empty input, single node, multiple trees, cycle, multiple parents, self-loop, and duplicate edges.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.