Katkat
Back

Compute shortest path with obstacles

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute shortest path with obstacles states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given an m×n grid with nonnegative cell costs and blocked cells marked '#'. You may move up, down, left, or right. Given start (sx, sy) and target (tx, ty), compute the minimum total cost path that avoids obstacles, or return -1 if unreachable. Implement an O(mn log mn) solution using Dijkstra’s algorithm with a priority queue, and explain how you would reconstruct the path.