Facebook Interview Question
SDE1sCountry: United States
package Main;
public class MinPath {
public static void main(String[] args) {
int xStart = 4, yStart = 4;
int xEnd = 0, yEnd = 2;
int[][] map = {{0, 1, 1, 0, 0},
{0, 0, 1, 0, 0},
{0, 1, 1, 1, 1},
{1, 1, 0, 0, 1},
{1, 1, 1, 1, 1}};
int[][] visitMap = {{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0}};
visitMap[xStart][yStart] = 1;
int length = new MinPath().path(map, visitMap, xStart, yStart, xEnd, yEnd);
System.out.println(length);
}
public int path(int[][] map, int[][] visitMap, int xStart, int yStart, int xEnd, int yEnd) {
visitMap[xStart][yStart] = 1;
//path does not exist
int length = 0;
if(xStart == xEnd && yStart == yEnd) {
return 1;
}
//move left
if(yStart - 1 > -1 && map[xStart][yStart - 1] == 1 && visitMap[xStart][yStart - 1] == 0){
int length1 = path(map, copy(visitMap), xStart, yStart-1, xEnd, yEnd);
if(length1 == 0) {
length = length > length1 ? length: length1;
}
else {
length1++;
if(length != 0) {
length = length > length1 ? length1 : length;
} else {
length = length1;
}
}
}
//move right
if(yStart + 1 < map[0].length && map[xStart][yStart + 1] == 1 && visitMap[xStart][yStart + 1] == 0){
int length2 = path(map, copy(visitMap), xStart, yStart + 1, xEnd, yEnd);
if(length2 == 0) {
length = length > length2 ? length: length2;
}
else {
length2++;
if(length != 0) {
length = length > length2 ? length2 : length;
} else {
length = length2;
}
}
}
//move upward
if(xStart - 1 > -1 && map[xStart-1][yStart] == 1 && visitMap[xStart-1][yStart] == 0){
int length3 = path(map, copy(visitMap), xStart-1, yStart, xEnd, yEnd);
if(length3 == 0) {
length = length > length3 ? length: length3;
}
else {
length3++;
if(length != 0) {
length = length > length3 ? length3 : length;
} else {
length = length3;
}
}
}
//move downward
return length;
}
public int[][] copy(int[][] original) {
int[][] c = new int[original.length][original[0].length];
for(int i=0; i<original.length; i++)
for(int j=0; j<original[0].length; j++)
c[i][j] = original[i][j];
return c;
}
}
package Main;
public class MinPath {
public static void main(String[] args) {
int xStart = 4, yStart = 4;
int xEnd = 0, yEnd = 2;
int[][] map = {{0, 1, 1, 0, 0},
{0, 0, 1, 0, 0},
{0, 1, 1, 1, 1},
{1, 1, 0, 0, 1},
{1, 1, 1, 1, 1}};
int[][] visitMap = {{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0}};
visitMap[xStart][yStart] = 1;
int length = new MinPath().path(map, visitMap, xStart, yStart, xEnd, yEnd);
System.out.println(length);
}
public int path(int[][] map, int[][] visitMap, int xStart, int yStart, int xEnd, int yEnd) {
visitMap[xStart][yStart] = 1;
//path does not exist
int length = 0;
if(xStart == xEnd && yStart == yEnd) {
return 1;
}
//move left
if(yStart - 1 > -1 && map[xStart][yStart - 1] == 1 && visitMap[xStart][yStart - 1] == 0){
int length1 = path(map, copy(visitMap), xStart, yStart-1, xEnd, yEnd);
if(length1 == 0) {
length = length > length1 ? length: length1;
}
else {
length1++;
if(length != 0) {
length = length > length1 ? length1 : length;
} else {
length = length1;
}
}
}
//move right
if(yStart + 1 < map[0].length && map[xStart][yStart + 1] == 1 && visitMap[xStart][yStart + 1] == 0){
int length2 = path(map, copy(visitMap), xStart, yStart + 1, xEnd, yEnd);
if(length2 == 0) {
length = length > length2 ? length: length2;
}
else {
length2++;
if(length != 0) {
length = length > length2 ? length2 : length;
} else {
length = length2;
}
}
}
//move upward
if(xStart - 1 > -1 && map[xStart-1][yStart] == 1 && visitMap[xStart-1][yStart] == 0){
int length3 = path(map, copy(visitMap), xStart-1, yStart, xEnd, yEnd);
if(length3 == 0) {
length = length > length3 ? length: length3;
}
else {
length3++;
if(length != 0) {
length = length > length3 ? length3 : length;
} else {
length = length3;
}
}
}
//move downward
return length;
}
public int[][] copy(int[][] original) {
int[][] c = new int[original.length][original[0].length];
for(int i=0; i<original.length; i++)
for(int j=0; j<original[0].length; j++)
c[i][j] = original[i][j];
return c;
}
}
public class dfs {
static int[][] map = {
{0, 1, 0},
{1, 1, 0,},
{1, 1, 1}};
static int shortP(int i, int j, int dx, int dy) {
if ( i >= map.length || j >= map.length || i < 0 || j < 0)
return 100000;
else if (map[i][j] == 0 )
return 100000;
else {
map[i][j] = 0;
if (i == dx && j == dy)
return 0;
return Math.min(
Math.min(shortP(i + 1, j, dx, dy) + 1, shortP(i, j + 1, dx, dy)) + 1,
Math.min(shortP(i - 1, j, dx, dy) + 1, shortP(i, j - 1, dx, dy) + 1));
}
}
public static void main(String[] arg) {
int l = shortP(1, 0, 2, 2);
System.out.println(l);
}
}
public class dfs {
static int[][] map = {
{0, 1, 0},
{1, 1, 0,},
{1, 1, 1}};
static int shortP(int i, int j, int dx, int dy) {
if ( i >= map.length || j >= map.length || i < 0 || j < 0)
return 100000;
else if (map[i][j] == 0 )
return 100000;
else {
map[i][j] = 0;
if (i == dx && j == dy)
return 0;
return Math.min(
Math.min(shortP(i + 1, j, dx, dy) + 1, shortP(i, j + 1, dx, dy)) + 1,
Math.min(shortP(i - 1, j, dx, dy) + 1, shortP(i, j - 1, dx, dy) + 1));
}
}
public static void main(String[] arg) {
int l = shortP(1, 0, 2, 2);
System.out.println(l);
}
}
public class dfs {
static int[][] map = {
{0, 1, 0},
{1, 1, 0,},
{1, 1, 1}};
static int shortP(int i, int j, int dx, int dy) {
if ( i >= map.length || j >= map.length || i < 0 || j < 0)
return 100000;
else if (map[i][j] == 0 )
return 100000;
else {
map[i][j] = 0;
if (i == dx && j == dy)
return 0;
return Math.min(
Math.min(shortP(i + 1, j, dx, dy) + 1, shortP(i, j + 1, dx, dy)) + 1,
Math.min(shortP(i - 1, j, dx, dy) + 1, shortP(i, j - 1, dx, dy) + 1));
}
}
public static void main(String[] arg) {
int l = shortP(1, 0, 2, 2);
System.out.println(l);
}
}
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class PathFinderUseDFS {
class Cell {
short x,y;
public Cell(short x, short y){
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Cell)) {
return false;
}
Cell c = (Cell) o;
return (x == c.x) && (y == c.y);
}
@Override
public int hashCode() {
return (new Short(x)).hashCode() + (new Short(y)).hashCode();
}
}
public static void main(String[] args){
short[][] testcase = {
{1,1,0,1},
{0,1,1,1},
{0,1,0,1},
{1,1,1,1}
};
// for DFS using recursive function leads to cleaner code
// vs handling the recursion stack during the interview
PathFinderUseDFS evaluator = new PathFinderUseDFS(testcase);
evaluator.findAndPrintShortestPath((short) 0, (short) 0, (short) 0, (short) 3);
}
short[][] grid;
int n,m;
List<Cell> shortestPath;
public PathFinderUseDFS(short[][] grid){
this.grid = grid;
n = grid.length;
m = grid.length;
}
public void findAndPrintShortestPath(
short startX, short startY,
short endX, short endY) {
// check start, end in grid
// check if start and end are valid cells
int maxDistance = n*m;
int distance[][] = new int[n][m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++) {
distance[i][j] = maxDistance;
}
}
List<Cell> currentPath = new LinkedList<Cell>();
Set<Cell> nodesInCurrentPath = new HashSet<Cell>();
Cell start = new Cell(startX, startY);
currentPath.add(start);
nodesInCurrentPath.add(start);
shortestPath = new LinkedList<Cell>();
findShortestPath(endX, endY,
start, currentPath, nodesInCurrentPath, distance);
// print shortest path
System.out.print("shortest path ");
for (Cell cell : shortestPath) {
System.out.print("(" + cell.x + "," + cell.y + ") ");
}
System.out.println();
}
public void findShortestPath(
short endX, short endY,
Cell cell, List<Cell> currentPath, Set<Cell> nodesInCurrentPath,
int[][] distance) {
// base cases
if (grid[cell.x][cell.y] == 0) {
return;
}
// check distance
// if smaller add neighbors
int currentPathLength = currentPath.size() - 1;
if (currentPathLength < distance[cell.x][cell.y]){
distance[cell.x][cell.y] = currentPathLength;
// base case
if ((cell.x == endX) && (cell.y == endY)) {
// update overall shortest path
shortestPath = new LinkedList<Cell>(currentPath);
return ;
}
List<Cell> neighbors = new LinkedList<Cell>();
if (cell.x - 1 >= 0) {
neighbors.add(new Cell((short)(cell.x-1), cell.y));
}
if (cell.x + 1 < n) {
neighbors.add(new Cell((short)(cell.x+1), cell.y));
}
if (cell.y - 1 >= 0) {
neighbors.add(new Cell(cell.x, (short)(cell.y-1)));
}
if (cell.y + 1 < m) {
neighbors.add(new Cell(cell.x, (short)(cell.y+1)));
}
for (Cell neighbor : neighbors) {
if (!nodesInCurrentPath.contains(neighbor)){
// update current path
currentPath.add(neighbor);
nodesInCurrentPath.add(neighbor);
findShortestPath(endX, endY,
neighbor, currentPath, nodesInCurrentPath, distance);
// undo changes to current path
currentPath.remove(neighbor);
nodesInCurrentPath.remove(neighbor);
}
}
}
}
}
- sgchris January 17, 2018