Graph Traversal for Pathfinding | Dataford Interview Questions

Amazon Robotics uses graph-like navigation models to represent reachable locations in a fulfillment center. Given an undirected or directed graph represented by an adjacency list, return the breadth-first traversal order starting from a specified node.

Your traversal must visit each reachable node at most once, preserve the neighbor order provided in the adjacency list, and safely handle cycles. If start is not present in the graph, return an empty list.

Formal Specification

Implement traverse_graph(graph, start), where graph is a dictionary mapping a node to a list of neighboring nodes, and start is the node from which traversal begins. Return a list containing every node reachable from start in breadth-first order. A neighbor that does not appear as a key in graph is treated as a leaf node.

Constraints

0 <= number of graph nodes <= 10^5
The graph has at most 2 * 10^5 adjacency entries
Node identifiers are hashable
Neighbor order must be preserved
Return only nodes reachable from start

Function Signature

def traverse_graph(graph, start):

Your question is Graph Traversal for Pathfinding. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

0 <= number of graph nodes <= 10^5
The graph has at most 2 * 10^5 adjacency entries
Node identifiers are hashable
Neighbor order must be preserved
Return only nodes reachable from start

Function Signature

def traverse_graph(graph, start):

Your question is Graph Traversal for Pathfinding. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.