Last active
December 23, 2018 20:00
An Amazon Technical interview question I received this year. Write a function that when given a map (a 2-dimensional grid where 1 is a walk-able square, 0 is an impassable square and 9 is the destination) and starting at the top left (x:0, y:0) finds the shortest path to the destination
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
public class Examples { | |
public static void main(String ... args) { | |
Solution s = new Solution(); | |
System.out.print("Example problem: "); | |
System.out.println(s.shortest(3, 3, | |
Arrays.asList( | |
Arrays.asList(1, 0, 0), | |
Arrays.asList(1, 0, 0), | |
Arrays.asList(1, 1, 9)))); | |
System.out.print("Example problem with 2 possible paths: "); | |
System.out.println(s.shortest(3, 3, | |
Arrays.asList( | |
Arrays.asList(1, 0, 0), | |
Arrays.asList(1, 1, 0), | |
Arrays.asList(1, 1, 9)))); | |
System.out.print("A direct path (EAST):"); | |
System.out.println(s.shortest(3, 1, | |
Arrays.asList( | |
Arrays.asList(1, 1, 9)))); | |
System.out.print("A direct path (SOUTH):"); | |
System.out.println(s.shortest(1, 3, | |
Arrays.asList( | |
Arrays.asList(1), | |
Arrays.asList(1), | |
Arrays.asList(9)))); | |
System.out.print("No path:"); | |
System.out.println(s.shortest(3, 3, | |
Arrays.asList( | |
Arrays.asList(1, 1, 1), | |
Arrays.asList(1, 1, 0), | |
Arrays.asList(1, 0, 9)))); | |
System.out.print("Path the walks in every direction at least once:"); | |
System.out.println(s.shortest(5, 4, | |
Arrays.asList( | |
Arrays.asList(1, 0, 1, 1, 1), | |
Arrays.asList(1, 0, 1, 0, 1), | |
Arrays.asList(1, 0, 1, 0, 1), | |
Arrays.asList(1, 1, 1, 0, 9)))); | |
System.out.print("Start at the end:"); | |
System.out.println(s.shortest(1, 1, | |
Arrays.asList( | |
Arrays.asList(9)))); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.List; | |
import java.util.PriorityQueue; | |
import java.util.Queue; | |
public class Solution { | |
public int shortest(int cols, int rows, List<List<Integer>> area) { | |
Point end = null; | |
// find the end | |
for (int row = 0; row < rows; row++) { | |
for (int col = 0; col < cols; col++) { | |
if (area.get(row).get(col) == 9) { | |
end = new Point(row, col); | |
break; | |
} | |
} | |
if (end != null) { | |
break; | |
} | |
} | |
// keep track of where I have been | |
boolean[][] visited = new boolean[rows][cols]; | |
Queue<Point> work = new PriorityQueue<>(); | |
work.add(new Point(0, 0, null, end)); | |
while(!work.isEmpty()) { | |
Point current = work.poll(); | |
if (current.isEnd(area)) { | |
return current.distanceToStart(); | |
} else { | |
// Look for each neighbor | |
// NORTH | |
if (current.row > 0 && area.get(current.row - 1).get(current.col) != 0 && visited[current.row - 1][current.col] == false) { | |
work.add(new Point(current.row - 1, current.col, current, end)); | |
visited[current.row - 1][current.col] = true; | |
} | |
// SOUTH | |
if (current.row < rows - 1 && area.get(current.row + 1).get(current.col) != 0 && visited[current.row + 1][current.col] == false) { | |
work.add(new Point(current.row + 1, current.col, current, end)); | |
visited[current.row + 1][current.col] = true; | |
} | |
// WEST | |
if (current.col > 0 && area.get(current.row).get(current.col - 1) != 0 && visited[current.row][current.col - 1] == false) { | |
work.add(new Point(current.row, current.col - 1, current, end)); | |
visited[current.row][current.col - 1] = true; | |
} | |
// EAST | |
if (current.col < cols - 1 && area.get(current.row).get(current.col + 1) != 0 && visited[current.row][current.col + 1] == false) { | |
work.add(new Point(current.row, current.col + 1, current, end)); | |
visited[current.row][current.col + 1] = true; | |
} | |
} | |
} | |
// we could'nt find a path use the String.indexOf sentinel | |
return -1; | |
} | |
class Point implements Comparable<Point> { | |
public final int row; | |
public final int col; | |
public final int distance; | |
public final Point parent; | |
public Point(int row, int col) { | |
this.row = row; | |
this.col = col; | |
this.distance = 0; | |
this.parent = null; | |
} | |
public Point(int row, int col, Point parent, Point end) { | |
this.row = row; | |
this.col = col; | |
this.parent = parent; | |
// Manhattan distance | |
this.distance = Math.abs(this.row - end.row) + Math.abs(this.col - end.col); | |
} | |
public String toString() { | |
return "("+this.row+","+this.col+")"; | |
} | |
public int distanceToStart() { | |
int distance = 0; | |
Point current = this; | |
while(current.parent != null) { | |
// System.out.println(current); | |
current = current.parent; | |
distance++; | |
} | |
// System.out.println("(0,0)"); | |
return distance; | |
} | |
public boolean isEnd(List<List<Integer>> area) { | |
// 9 is magic value of the end "end" | |
return area.get(this.row).get(this.col) == 9; | |
} | |
@Override | |
public int compareTo(Point that) { | |
return this.distance; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Example problem: 4 | |
Example problem with 2 possible paths: 4 | |
A direct path (EAST):2 | |
A direct path (SOUTH):2 | |
No path:-1 | |
Path the walks in every direction at least once:13 | |
Start at the end:0 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment