## Facebook Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

This can be achieved by simple graph search, Since for graph traversal, the already seen node needs to be identified to avoid search loop, (as oppose to trees where such condition does not exist), the marking the entry as 1 is used to avoid this

``````#include <iostream>
using namespace std;
#include <vector>

bool is_invalid_or_reached(vector< vector<int> > &v, int cx, int cy) {
if (cx < 0 || cy < 0 || (cx >= v.size()) ||
(cy >= v[cx].size()) || v[cx][cy] == 1) {
return false;
}

return true;

}
bool find_path(vector< vector<int> > &v, int cx, int cy) {
if (!is_invalid_or_reached(v, cx, cy)) {
return false;
}
if (v[cx][cy] == 2 ) {
cout << "Found at " << cx << ":" << cy <<"\n";
return true;
}

// cx and cy is valid
v[cx][cy] = 1;
return find_path(v, cx-1, cy) || find_path(v, cx, cy-1) ||
find_path(v, cx+1, cy) || find_path(v, cx, cy+1);

}

int main() {
vector< vector<int> > i(10, vector<int>(10));
i[8][6] = 2;
find_path(i, 5, 2);

return 0;
}``````

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

``````public class HasPathInMaze {

private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public static boolean hasPath(char[][] matrix){
if(matrix.length == 0 || matrix[0].length == 0) return false;

int N = matrix.length;
boolean[][] visited = new boolean[N][N];

for(int i = 0; i< N; i++){
for(int j = 0 ;j < N ; j++){
if(matrix[i][j] == 'R'){
if(hasPathUtil(matrix, visited, i, j, N)){
return true;
}
}
}
}

return false;
}

private static boolean hasPathUtil(char[][] matrix, boolean[][] visited, int row, int col, int N){
if(row< 0 || row >=N || col < 0 || col >=N || visited[row][col] || matrix[row][col] == 'X') return false;

if(matrix[row][col] == 'T') return true;

visited[row][col] = true;

for(int[] dir : dirs){
int i = dir[0] + row;
int j = dir[1] + col;

if(hasPathUtil(matrix, visited, i, j, N)){
return true;
}
}

visited[row][col] = false;
return false;
}

public static void main(String[] args) {

char[][] maze = {
{'X', '_', '_', 'R', '_', 'X'},
{'X', '_', 'X', 'X', 'X', '_'},
{'_', '_', '_', '_', '_', '_'},
{'_', 'X', 'X', '_', 'X', 'X'},
{'X', 'T', '_', '_', 'X', '_'}
};

System.out.println(hasPath(maze));
}
}``````

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

Using a stack to spread the search

``````public static bool CanReach(char[,] matrix)
{
if (matrix == null)
return false;

int m = matrix.GetLength(0);
int n = matrix.GetLength(1);
var stack = new Stack<Tuple<int, int>>();

for (int i=0; i < m; i++)
{
for (int j=0; j < n; j++)
{
if (matrix[i,j] == 'R')
{
stack.Push(Tuple.Create(i, j));
break;
}
}

if (stack.Count > 0)
break;
}

while (stack.Count > 0)
{
var t = stack.Pop();
if (matrix[t.Item1, t.Item2] == 'T')
return true;

matrix[t.Item1, t.Item2] = 'V';

if (IsValidCell(t.Item1, t.Item2-1, matrix))
stack.Push(Tuple.Create(t.Item1,t.Item2-1));
if (IsValidCell(t.Item1, t.Item2+1, matrix))
stack.Push(Tuple.Create(t.Item1,t.Item2+1));
if (IsValidCell(t.Item1-1, t.Item2, matrix))
stack.Push(Tuple.Create(t.Item1-1, t.Item2));
if (IsValidCell(t.Item1+1, t.Item2, matrix))
stack.Push(Tuple.Create(t.Item1+1, t.Item2));
}

for (int i=0; i < m; i++)
for (int j=0; j < n; j++)
if (matrix[i,j] == 'V')
matrix[i,j] = ' ';

return false;
}

private static bool IsValidCell(int i, int j, char[,] matrix)
{
if (i < 0 || i >= matrix.GetLength(0) || j < 0 || j >= matrix.GetLength(1))
return false;

return matrix[i,j] != 'X' && matrix[i,j] != 'V';
}``````

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

Using a stack to spread the search

``````public static bool CanReach(char[,] matrix)
{
if (matrix == null)
return false;

int m = matrix.GetLength(0);
int n = matrix.GetLength(1);
var stack = new Stack<Tuple<int, int>>();

for (int i=0; i < m; i++)
{
for (int j=0; j < n; j++)
{
if (matrix[i,j] == 'R')
{
stack.Push(Tuple.Create(i, j));
break;
}
}

if (stack.Count > 0)
break;
}

while (stack.Count > 0)
{
var t = stack.Pop();
if (matrix[t.Item1, t.Item2] == 'T')
return true;

matrix[t.Item1, t.Item2] = 'V';

if (IsValidCell(t.Item1, t.Item2-1, matrix))
stack.Push(Tuple.Create(t.Item1,t.Item2-1));
if (IsValidCell(t.Item1, t.Item2+1, matrix))
stack.Push(Tuple.Create(t.Item1,t.Item2+1));
if (IsValidCell(t.Item1-1, t.Item2, matrix))
stack.Push(Tuple.Create(t.Item1-1, t.Item2));
if (IsValidCell(t.Item1+1, t.Item2, matrix))
stack.Push(Tuple.Create(t.Item1+1, t.Item2));
}

for (int i=0; i < m; i++)
for (int j=0; j < n; j++)
if (matrix[i,j] == 'V')
matrix[i,j] = ' ';

return false;
}

private static bool IsValidCell(int i, int j, char[,] matrix)
{
if (i < 0 || i >= matrix.GetLength(0) || j < 0 || j >= matrix.GetLength(1))
return false;

return matrix[i,j] != 'X' && matrix[i,j] != 'V';
}``````

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

Python version using a stack keeping track of the last visited position to avoid infinite paths (some cases would require a set of visited positions or modify the matrix).

``````def find_maze_exit(maze, start, end):
frontier = [ (start, start) ]
while len(frontier) > 0:
current, last = frontier.pop()
if current == end:
return True

for x, y in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
n_p = (current[0] + x, current[1] + y)
if n_p[0] < 0 or n_p[0] >= len(maze)\
or n_p[1] < 0 or n_p[1] >= len(maze[x])\
or n_p == last or maze[n_p[0]][n_p[1]] == 'X':
continue

frontier.append((n_p, current))

return False``````

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

bool findpath(char ar[200][],int i, int j)
{
if(ar[i][j--]=='X' && ar[i][j++]=='X' && ar[i--][j]=='X' && ar[i++][j]=='X')
return false;
if(ar[i][j--]=='T' || ar[i][j++]=='T' || ar[i--][j]=='T' || ar[i++][j]=='T')
return true;
else
{
if(ar[i][j--]=="_")
findpath(ar,i,j--);
if(ar[i][j++]=="_")
findpath(ar,i,j++);
if(ar[i--][j]=="_")
findpath(ar,i--,j);
if(ar[i++][j]=="_")
findpath(ar,i++,j);
}
return false;
}
int main()
{
char ar[200][200];
int initr,endr;
for(int i=0;i<200;i++)
for(int j=0;j<200;j++)
cin>>ar[i][j];
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(ar[i][j]=='R')
{
initr=i;
endr=j;
break;
}
bool x=findpath(ar,initr,endr);
if(x == true)
cout<<"YES";
else
cout<<"NO";
return 0;
}

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

BFS works?

``````public class Reach {

public boolean isPath(char[][] maze) {
boolean[][] visited = new boolean[maze.length][maze[0].length];
boolean result = false;
for(int i = 0; i < maze.length; i++)
for(int j = 0; j < maze[0].length; j++) {
if(maze[i][j] == 'R')
result = bfs(maze, i, j, visited);
}
return result;
}

public boolean bfs(char[][] maze, int i, int j, boolean[][] visited) {
Point p = new Point(i, j);
Queue<Point> queue = new LinkedList<>();

while(!queue.isEmpty()) {
Point temp = queue.poll();
int x = temp.x;
int y = temp.y;
if(maze[x][y] == 'T')
return true;
visited[x][y] = true;

if(x > 0 && !visited[x-1][y]) {
Point newPoint = (checkPoint(maze, x-1, y));
if(newPoint != null)
}
if(y > 0 && !visited[x][y-1]) {
Point newPoint = (checkPoint(maze, x, y-1));
if(newPoint != null)
}
if(x < maze.length-1 && !visited[x+1][y]) {
Point newPoint = (checkPoint(maze, x+1, y));
if(newPoint != null)
}
if(y < maze[0].length-1 && !visited[x][y+1]) {
Point newPoint = (checkPoint(maze, x, y+1));
if(newPoint != null)
}
}
return false;
}

public Point checkPoint(char[][] maze, int x, int y) {
if(maze[x][y] == 'X')
return null;
return new Point(x, y);
}

public static void main(String[] args) {

char[][] maze = {
{'_', 'X', 'R', '_', '_'},
{'_', '_', '_', 'X', '_'},
{'_', 'X', '_', 'X', 'X'},
{'_', 'X', '_', '_', 'T'}
};

Reach m = new Reach();

System.out.println(m.isPath(maze));
}
}``````

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.