How should I practice Deterministic Depth-First Graph Traversal?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Waymo phone screen problems in FastPrep.

Is Deterministic Depth-First Graph Traversal associated with Waymo?

FastPrep tags this as a Waymo phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Deterministic Depth-First Graph Traversal

Learn this problem

● Medium

WaymoFULLTIMEPHONE SCREEN

Problem statement

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.