Shortest Distance in Graph | Dataford Interview Questions

Design an algorithm to get the shortest distance between two nodes in a graph (high level); how do BFS and DFS differ and what are the tradeoffs?

Asked in the phone interview stage.

Implement shortest_distance(graph, start, target), where graph is a dictionary mapping each node to a list of neighboring nodes. Return the minimum number of edges from start to target, or -1 if no path exists. Assume the graph is unweighted and directed. The function should return 0 when start == target.

Constraints

The graph is directed and unweighted.
1 <= number of nodes <= 10^4.
0 <= number of edges <= 10^5.
Node identifiers are hashable.
The adjacency lists may contain cycles and repeated references are not assumed to be present.

Function Signature

def shortest_distance(graph, start, target):

Your question is Shortest Distance in Graph. 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

Design an algorithm to get the shortest distance between two nodes in a graph (high level); how do BFS and DFS differ and what are the tradeoffs?

Asked in the phone interview stage.

Constraints

The graph is directed and unweighted.
1 <= number of nodes <= 10^4.
0 <= number of edges <= 10^5.
Node identifiers are hashable.
The adjacency lists may contain cycles and repeated references are not assumed to be present.

Function Signature

def shortest_distance(graph, start, target):

Your question is Shortest Distance in Graph. 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.