All Paths Between Two Points | Dataford Interview Questions

Print all the paths present between 2 points in a graph.

Asked in the Round 1 stage. Reported follow-up: print only the shortest paths.

Implement all_paths(graph, start, end). graph is a dictionary mapping each vertex to a list of directly reachable vertices. Return a list of paths, where each path is a list of vertices from start to end. A path may not repeat a vertex. Return an empty list when no path exists. The output order may follow DFS traversal order.

Constraints

The graph is directed and contains at most 15 vertices.
Vertex names are strings.
All referenced vertices appear as keys in graph.
A path cannot repeat a vertex.
The result may contain exponentially many paths.

Function Signature

def all_paths(graph, start, end):

Your question is All Paths Between Two Points. 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

Print all the paths present between 2 points in a graph.

Asked in the Round 1 stage. Reported follow-up: print only the shortest paths.

Constraints

The graph is directed and contains at most 15 vertices.
Vertex names are strings.
All referenced vertices appear as keys in graph.
A path cannot repeat a vertex.
The result may contain exponentially many paths.

Function Signature

def all_paths(graph, start, end):

Your question is All Paths Between Two Points. 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.