Facebook Interview Question
SDE1sCountry: United States
import java.io.*;
import java.util.*;
import java.awt.Point;
class Solution {
static String source = "3 10" + "\n" + "3" + "\n" + "1 2" + "\n" + "1 5" + "\n" + "1 8" + "\n" + "0 0" + "\n" + "1 7";
private int M;
private int N;
private List<Point> hurdles;
private int si, sj;
private int ei, ej;
public Solution(int nbHurdles) {
this.hurdles = new ArrayList<Point>(nbHurdles);
}
public static void main(String[] args) {
Scanner in = new Scanner(source);
int M = in.nextInt();
int N = in.nextInt();
System.out.println(M + " " + N);
int nbHurdles = in.nextInt();
System.out.println("Hurdles " + nbHurdles);
Solution s = new Solution(nbHurdles);
s.M = M; s.N = N;
for(int x = 0; x < nbHurdles; x++) {
int i = in.nextInt();
int j = in.nextInt();
s.hurdles.add(new Point(i, j));
System.out.println(i + " " + j);
}
s.si = in.nextInt();
s.sj = in.nextInt();
System.out.println("Start from " + s.si + " " + s.sj);
s.ei = in.nextInt();
s.ej = in.nextInt();
System.out.println("End at " + s.ei + " " + s.ej);
int size = s.run();
System.out.println("Max length is "+size);
}
/*
*/
public boolean isValid(List<Point> points, int i, int j) {
if(i<0 || i>=this.M || j<0 || j>=this.N)
return false;
for(Point p: points) {
if(p.x==i && p.y==j) return false;
}
return true;
}
/**/
public int run() {
if(si==ei && sj==ej)
return -1;
if(!(isValid(this.hurdles, si, sj) && isValid(this.hurdles, ei, ej)))
return -1;
return visitChildren(new ArrayList<Point>(), this.si, this.sj);
}
public int visitChildren(List<Point> path, int i, int j) {
if(isValid(this.hurdles, i, j)==false) {
return -1;
}
if(i==this.ei && j==this.ej) {
return path.size();
}
path.add(new Point(i, j));
int max = 0;
if(isValid(path, i+1, j)) {
max = Math.max(max, visitChildren(new ArrayList<Point>(path), i+1, j));
};
if(isValid(path, i, j+1)) {
max = Math.max(max, visitChildren(new ArrayList<Point>(path), i, j+1));
}
if(isValid(path, i-1, j)) {
max = Math.max(max, visitChildren(new ArrayList<Point>(path), i-1, j));
}
if(isValid(path, i, j-1)) {
max = Math.max(max, visitChildren(new ArrayList<Point>(path), i, j-1));
}
return max;
}
}
- Eric August 07, 2016