FastPrepDeterministic Depth-First Graph Traversal
Problems/Deterministic Depth-First Graph Traversal

Deterministic Depth-First Graph Traversal

Waymo logoWaymo● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The source asks for a depth-first graph traversal and a correctness proof but omits graph direction, representation, start and component rules, neighbor order, output format, and bounds. The judged core task is an approximately 72% match.

You are given a directed graph as adjacency, where vertices are numbered from 0 through adjacency.length - 1. The neighbors in each input list may appear in any order.

Starting at start, perform a depth-first traversal. Whenever a vertex has several unvisited outgoing neighbors, visit the neighbor with the smallest vertex number first.

Return the vertices in preorder: append a vertex when it is first discovered. Visit every reachable vertex exactly once and omit vertices that are unreachable from start.

Function

dfsTraversal(adjacency: int[][], start: int) → int[]

Examples

Example 1

adjacency = [[2,1],[3],[3],[1],[]]start = 0return = [0,1,3,2]

From 0, vertex 1 is chosen before 2. The traversal follows 1 to 3, then backtracks to visit 2. Vertex 4 is unreachable.

Example 2

adjacency = [[1],[2],[0,3],[]]start = 2return = [2,0,1,3]

At 2, neighbor 0 is explored before 3. The cycle back to 2 is ignored because 2 is already visited.

Example 3

adjacency = [[],[0],[1]]start = 0return = [0]

The start vertex has no outgoing edge, so the traversal contains only that vertex.

Constraints

  • 1 <= adjacency.length <= 100000.
  • 0 <= start < adjacency.length.
  • Every neighbor is a valid vertex, every directed edge appears at most once, and the graph may contain cycles or self-loops.
  • The total number of directed edges is at most 200000.

More Waymo problems

  • Fixed-Order Task Run Time With CooldownPHONE SCREEN · Seen Oct 2026
  • Reorderable Task Scheduler With CooldownPHONE SCREEN · Seen Oct 2026
  • Island Area and Water BoundaryPHONE SCREEN · Seen Sep 2026
All Waymo interview questionsSee Waymo hiring insights
Saved
class Solution {
    public int[] dfsTraversal(int[][] adjacency, int start) {
        // Write your code here.
    }
}
Checking account…