How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Compute shortest path with obstacles | Amazon Coding Question

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.

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

Expected Output: -1

Explanation: Both off-diagonal cells are blocked, so the target at (1,1) is completely walled off from the start; unreachable returns -1.

Input: (["5"], 0, 0, 0, 0)

Expected Output: 5

Explanation: Start equals target in a single-cell grid; the path is just that one cell, costing 5.

Input: (["000","110","000"], 0, 0, 2, 0)

Expected Output: 0

Explanation: Going straight down costs 0+1+0=1, but detouring across the zero-cost border (right along the top, down the right column, left along the bottom) costs 0; the min is 0.

Input: (["#1","11"], 0, 0, 1, 1)

Expected Output: -1

Explanation: The start cell (0,0) is itself an obstacle, so no path exists and the answer is -1.

Input: (["12","21"], 0, 0, 1, 1)

Expected Output: 4

Explanation: Both routes from (0,0) to (1,1) cost the same: 1+2+1 = 4 going via either the top-right or bottom-left cell.

Hints

Cell costs are nonnegative, so Dijkstra applies: always expand the lowest-total-cost cell discovered so far from a min-heap.
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).
Skip stale heap entries (when the popped distance exceeds the recorded best for that cell) and never step onto a '#' or out of bounds.
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.

Quick Overview