Quick Overview

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.

Compute shortest path with obstacles

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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 x n grid, supplied as an array of m equal-length strings. Each character is either a digit '0'-'9' giving the nonnegative cost of entering that cell, or '#' marking a blocked obstacle you may never enter. From a cell you may move up, down, left, or right (no diagonals) to an adjacent in-bounds, non-blocked cell. The cost of a path is the sum of the entry costs of every cell it visits, including both the start cell and the target cell. Given the start coordinates (sx, sy) and target coordinates (tx, ty) (row, column), return the minimum total cost of any path from start to target that avoids obstacles, or -1 if the target is unreachable (or if the start or target is itself blocked or out of bounds). Implement an O(mn log mn) solution using Dijkstra's algorithm with a priority queue. Path reconstruction: while relaxing, store a parent pointer for each cell when its best distance improves. After the search, if the target was reached, walk the parent pointers backward from the target to the start and reverse the sequence to recover the actual cells of the cheapest path.

Constraints

  • 1 <= m, n; all rows of grid have the same length n
  • Each grid character is a digit '0'-'9' (cell entry cost) or '#' (blocked)
  • 0 <= sx, tx < m and 0 <= sy, ty < n in valid inputs; out-of-range or blocked start/target returns -1
  • Movement is 4-directional (up, down, left, right); no diagonals
  • Path cost includes the entry cost of both the start and the target cells
  • Return -1 when the target cannot be reached

Examples

Input: (["123","456","789"], 0, 0, 2, 2)

Expected Output: 21

Explanation: Cheapest corner-to-corner path is 1->2->3->6->9 (right, right, down, down), summing every visited cell's cost: 1+2+3+6+9 = 21.

Input: (["1#1","1#1","111"], 0, 0, 0, 2)

Expected Output: 7

Explanation: A wall of '#' separates the two top cells, so the only route is down the left column, across the bottom row, and up the right column: 1+1+1+1+1+1+1 = 7.

Hints

  1. Cell costs are nonnegative, so Dijkstra applies: always expand the lowest-total-cost cell discovered so far from a min-heap.
  2. Treat each non-blocked cell as a graph node; the weight of moving into a neighbor is that neighbor's own entry cost. Seed dist[start] with the start cell's cost and push (startCost, sx, sy).
  3. Skip stale heap entries (when the popped distance exceeds the recorded best for that cell) and never step onto a '#' or out of bounds.
  4. To reconstruct the path, record a parent for each cell whenever you improve its distance; after reaching the target, follow parents back to the start and reverse.

Loading coding console...