CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

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;
}

- ali.kheam May 26, 2017 | Flag Reply
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));
    }
}

- aravindbros May 31, 2017 | Flag Reply
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';
}

- Anonymous May 26, 2017 | Flag Reply
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';
}

- hnatsu May 26, 2017 | Flag Reply
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

- Fernando May 26, 2017 | Flag Reply
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;
}

- aishwaryassr May 29, 2017 | Flag Reply
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<>();

        queue.add(p);

        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)
                    queue.add(newPoint);
            }
            if(y > 0 && !visited[x][y-1]) {
                Point newPoint = (checkPoint(maze, x, y-1));
                if(newPoint != null)
                    queue.add(newPoint);
            }
            if(x < maze.length-1 && !visited[x+1][y]) {
                Point newPoint = (checkPoint(maze, x+1, y));
                if(newPoint != null)
                    queue.add(newPoint);
            }
            if(y < maze[0].length-1 && !visited[x][y+1]) {
                Point newPoint = (checkPoint(maze, x, y+1));
                if(newPoint != null)
                    queue.add(newPoint);
            }
        }
        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));
    }
}

- KC May 31, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More