Graph Traversal for Networks | Dataford Interview Questions

Altana's supply chain graph represents entities such as suppliers, manufacturers, and logistics hubs as nodes, with directed relationships as edges. Given this graph, return the shortest path from a starting entity to a target entity using breadth-first search.

If the target cannot be reached, return an empty list. The path must include both the start and target nodes. Neighbor lists should be processed in the order provided, so the returned path is deterministic when multiple shortest paths exist.

Formal Specification

Implement find_shortest_path(graph, start, target), where graph is a dictionary mapping strings to lists of neighboring entity IDs. Return a list of strings representing the shortest directed path, or [] when no path exists.

Constraints

1 <= number of distinct entities <= 10^5
0 <= number of directed relationships <= 2 * 10^5
Entity IDs are non-empty strings
The graph may contain cycles and disconnected components
A neighbor may appear without having its own key in graph

Function Signature

def find_shortest_path(graph, start, target):

Your question is Graph Traversal for Networks. 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

1 <= number of distinct entities <= 10^5
0 <= number of directed relationships <= 2 * 10^5
Entity IDs are non-empty strings
The graph may contain cycles and disconnected components
A neighbor may appear without having its own key in graph

Function Signature

def find_shortest_path(graph, start, target):

Your question is Graph Traversal for Networks. 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.