Unit Testing and Algorithms | Dataford Interview Questions

Describe how you implement unit tests and apply data structures and algorithms to solve a problem.

Implement shortest_path(graph, start, end) using an appropriate data structure and algorithm. The graph is a directed adjacency map whose values are [neighbor, weight] pairs. Return the nodes in a minimum-weight path from start to end, or [] when no path exists. Explain the unit tests you would use, including normal cases, boundary cases, and unreachable nodes.

Constraints

1 <= number of graph nodes <= 1000
0 <= number of directed edges <= 5000
Edge weights are nonnegative integers
Every neighbor listed in an edge is a valid graph node or may be absent from the map with no outgoing edges
Return any minimum-weight path when multiple paths have the same cost

Function Signature

def shortest_path(graph, start, end):

Your question is Unit Testing and Algorithms. 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

Describe how you implement unit tests and apply data structures and algorithms to solve a problem.

Constraints

1 <= number of graph nodes <= 1000
0 <= number of directed edges <= 5000
Edge weights are nonnegative integers
Every neighbor listed in an edge is a valid graph node or may be absent from the map with no outgoing edges
Return any minimum-weight path when multiple paths have the same cost

Function Signature

def shortest_path(graph, start, end):

Your question is Unit Testing and Algorithms. 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.