Minimum Distance Required for Truck to Deliver Order [Amazon Coding Question]
Problem Statement: Find the shortest path to reach the destination in the matrix (Amazon Delivery Coding Challenge)
Amazon Fresh is a grocery delivery service that offers consumers the option of purchasing their groceries online and having them delivered on schedule. The Amazon Fres team is planning a route for a delivery truck to deliver customer orders in the city of Techland. The planner will create a delivery area for each order to effectively plan the route. The area is abstracted as a grid. Not all locations are accessible by road. The truck only needs to make a single delivery.
Write an algorithm to determine the minimum distance required for the truck to deliver the order.
- Some places in the delivery area cannot be accessed by the driver as there are no roads in those locations.
- The delivery area can be represented as a two-dimensional grid of integers where each integer represents one cell.
- The truck must start from the top-left corner of the area which is always accessible, and can move one cell up, down., left or right at a time.
- Tne trucks must navigate around the area without roads and cannot leave the area.
- The accessible areas are represented as 1, an area with without roads is represented by 0 and the destination is represented by 9.
The input to the function/method consists of three arguments numRows, an integer representing the number of rows, numColumns, an integer representing the number of columns, area, representing the two-dimensional grid of integers.
Return an integer representing the total distance traversed to deliver the order; else return -1
1<= numRows, numColumns<=1000
numRows=3 numColumns=3 area [[1, 0, 0] [1, 0, 0] [1, 9, 1]]
Starting from the top-left corner, the truck traversed the cell
(0, 0)-> (1,0)->(2,0)->(2,1)
The truck traversed the total distance 3 to deliver the order, so the output is 3.
There are multiple ways to solve this coding challenge. Before reading the solution, I would recommend you to find your own solution.
If you find the solution it is well and good. Otherwise, here is I’m giving you the simple solution.
- It is difficult to handle and traverse the matrix. The easiest way is to convert it into the single array list.
like [1, 0, 0, 1, 0, 0, 1, 9, 1].
- Visting next element (left) is possible by adding one (i->i+1).
- The visiting element in the next row is possible by adding a number of columns (i->i+columns).
Minimum Distance Required for the Truck to Deliver the Order
You can implement this logic and solve this problem in any of the programming languages like C/C++, Java, and Python.
def minDistance(grid, cur, col): if grid[cur]==9: return 0 rInd=cur+1 dInd=cur+col if rInd<len(grid) and dInd<len(grid) and grid[rInd]>0 and grid[dInd]>0: return 1+min(minDistance(grid, rInd, col), minDistance(grid, dInd, col)) elif rInd<len(grid) and grid[rInd]>0: return 1+minDistance(grid, rInd, col) elif dInd<len(grid) and grid[dInd]>0: return 1+minDistance(grid, dInd, col) else: return len(grid) def findShortedtPath(grid, rows, columns): liPath= for i in grid: liPath.extend(i) val=minDistance(liPath, 0, columns) if val<=len(liPath): print(val) else: print(-1) findShortedtPath([[1, 0, 0], [1, 0, 0], [1, 9, 1]], 3, 3) findShortedtPath([[1, 1, 1], [0, 1, 1], [1, 0, 1], [1, 9, 1]], 4, 3) findShortedtPath([[1, 0, 0], [1, 0, 0], [0, 9, 1]], 3, 3)
3 6 -1
Note: Check the else-statement in the
minDistance() method. I’m returning
len(grid). You can always use any value which is bigger than the maximum length of the path.
If the length of the path is greater than
len(grid), there is no valid path to reach the destination and print
There was one more question was asked in the Amazon coding round- Minimum Cost of Merging Files.
In the Amazon interview, they can ask you to calculate the complexity of the algorithm. So be prepared for this if you are shortlisted for the interview round.
To solve this type of challenge, you have to be good at …
This is all about the program for finding the minimum distance required for the truck to deliver the order.
In this tutorial, I have shared the Python program to find the shortest path to reach the destination in the matrix asked in the Amazon coding test. If you can solve it in any other programming languages like Java or C/C++, share it with me in the comment. I will mention your code in this tutorial.
All the best!