Skip to content

Instantly share code, notes, and snippets.

@jasonsperske
Last active December 23, 2018 20:00
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jasonsperske/ef1367273aa1e1a7bdab68be9e4c13f9 to your computer and use it in GitHub Desktop.
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
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))));
}
}
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;
}
}
}
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