## Facebook Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
2
of 4 vote

``````import java.util.Scanner;
public class FindLongestPath2 {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int M = scan.nextInt();
int N = scan.nextInt();
boolean[][] map = new boolean[M][N];

int H = scan.nextInt();
for(int h = 0; h<H; h++) {
int hy = scan.nextInt();
int hx = scan.nextInt();
map[hy][hx] = true;
}

int sy = scan.nextInt();
int sx = scan.nextInt();

int gy = scan.nextInt();
int gx = scan.nextInt();

int ans = getLongestPath(map, new boolean[M][N], sx, sy, gx, gy);

System.out.println(ans -1);

scan.close();
}

static int getLongestPath(boolean[][] map, boolean[][] history, int sx, int sy, int gx, int gy) {
if(sy >= map.length || sx >= map[0].length || sy < 0 || sx < 0)
return 0;

if(map[sy][sx] == true || history[sy][sx] == true) {
return 0;
}

if(sx == gx && sy == gy)
return 1;

history[sy][sx] = true;

int up = getLongestPath(map, copy2D(history), sx, sy+1, gx, gy);
int down = getLongestPath(map, copy2D(history), sx, sy-1, gx, gy);
int left = getLongestPath(map, copy2D(history), sx-1, sy, gx, gy);
int right = getLongestPath(map, copy2D(history), sx+1, sy, gx, gy);

int max = Math.max(Math.max(left, right), Math.max(up, down));

if(max == 0)
return -1;

return max + 1;
}

static boolean[][] copy2D(boolean[][] history) {
boolean[][] copy = new boolean[history.length][];
for(int i=0; i<history.length; i++) {
copy[i] = history[i].clone();
}
return copy;
}
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();
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();
}
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;
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.