Core Data Structures and Algorithms | Dataford Interview Questions

How would you apply standard data structures and algorithms to solve a robotics engineering problem?

Implement a shortest-path solver for a rectangular occupancy grid using standard algorithmic techniques. Cells with 0 are traversable, and cells with 1 are blocked. Return a shortest four-directional path from start to goal, inclusive, or an empty list if no path exists.

Function: def shortest_path(grid, start, goal)

Input shapes: grid is a non-empty list of equal-length row lists, and start and goal are [row, column] lists. The output is a list of [row, column] lists.

Constraints

1 <= len(grid) <= 100
1 <= len(grid[0]) <= 100
All grid rows have the same length
Each grid value is either 0 or 1
start and goal are valid grid coordinates
Movement is allowed only up, down, left, and right

Function Signature

def shortest_path(grid, start, goal):

Your question is Core Data Structures 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