Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

This can be solved by Simple Depth First Search using Recursion..

// 8 Adjacent points
int dx[]={+0,+0,+1,-1,+1,+1,-1,-1};
int dy[]={+1,-1,+0,+0,+1,-1,+1,-1};

bool visited[50][50];
string grid[50];
int m=50,n=50;
bool dfs(int x,int y){
	if(grid[x][y]=='X')return 1;
	bool res=0;
	visited[x][y]=1;
	for(int i=0;i<8;i++){
		int newx=x+dx[i];
		int newy=y+dy[i];
                // Check whether the new point is valid one ..
		if(newx>=0 && newy>=0 && newx<m && newy<n){
                       // Check whether it is visited already / it is not 'W'
			if(visited[newx][newy]==0 && grid[x][y]!='W')
				res|=(dfs(newx,newy));
		}
	}
	return res;
}
bool solve(){
	int startx=0,starty=0;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(grid[i][j]=='O'){
				startx=i,starty=j;
				break;
			}
		}
	}
	return dfs(startx,starty);
}

- Krish April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Given the matrix
. .
. .
. .
. .
. .
X O
. .
. .
you algorithm will go up as far as it can go and then will go down, and then find X.
It is a good solution and often the best choice, but given maze routing problems, you have a better shot at finding the target faster using BFS (see lee algorithm)

- ep0 April 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice, clear code, Krish. One thing to improve: after a path is found, return immediately to save searching the rest of the maze. That is, in the code above replace:

res|=(dfs(newx,newy));

with

if (dfs(newx, newy)) return true;

- corneliu July 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Why do you guys start writing code directly?
Please write your approach in the form of words and than write the code with comments to let the people understand clearly & quickly.

- Grover June 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Can be solved by backtracking.
call with

x,y indices of 'o'
dest - 'x'
err - 'w'
visited - boolean array to track visited nodes.

boolean inbounds(int x, int y, boolean[][] visited) {
		if (x >= 0 && x < visited.length && y >= 0 && y < visited[0].length
				&& !visited[x][y])
			return true;
		else
			return false;
	}

	boolean pathExists(int x, int y, char a[][], boolean visited[][],
			char dest, char err) {
		visited[x][y] = true;
		boolean right = false, left = false, up = false, down = false, ludiag = false, rudiag = false, lddiag = false, rddiag = false;
		if (a[x][y] == dest)
			return true;
		else if (a[x][y] == err)
			return false;
		else {
			if (inbounds(x + 1, y, visited)) {
				right = pathExists(x+1, y, a, visited, dest, err);
			}

			if (inbounds(x, y + 1, visited)) {

				down = pathExists(x, y+1, a, visited, dest, err);
			}

			if (inbounds(x + 1, y + 1, visited)) {
				rddiag = pathExists(x+1, y+1, a, visited, dest, err);
			}
			if (inbounds(x - 1, y, visited)) {
				left = pathExists(x-1, y, a, visited, dest, err);
			}
			if (inbounds(x, y - 1, visited)) {
				up = pathExists(x, y-1, a, visited, dest, err);
			}
			if (inbounds(x - 1, y - 1, visited)) {
				ludiag = pathExists(x-1, y-1, a, visited, dest, err);
			}
			if (inbounds(x + 1, y - 1, visited)) {
				rudiag = pathExists(x+1, y-1, a, visited, dest, err);
			}
			if (inbounds(x - 1, y + 1, visited)) {
				lddiag = pathExists(x-1, y+1, a, visited, dest, err);
			}

		}
		return left||right||up||down||ludiag||rudiag||lddiag||rddiag;
	}

- Kiruba April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

everyone... please explain your logic ..ther is no use of code..no one is gonna sit & read the big code...
so try to mention the logic /important aspects of program.. so that everyone understands.

- amnesiac June 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

We can use A* algorithm which takes euclidean distance as heuristic... very fast..

- amnesiac June 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if anyone wants code i ll submit it..

- amnesiac June 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If simply use euclidean distance as heuristic to implement the A* algorithm, what will be the difference with BFS?

- Baibing November 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

. . . . . . .
. . . . . . .
w . . . . . .
w .w.w..
. . . . O . .
. . w. . . .
. . . X . . .

it is a simple graph reachability problem.
here the character matrix can be plotted as a graph where ..... shows the nodes are connected. while w shows disconnected.
we can apply dfs/bfs from the source node and if we reach a node w, then return else recurse for each connected node,if we reach X,then true else false.

- nk August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

isn't Rat In Maze problem. And can be solved using backtracking.

- techcoder April 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use A* algo solve this problem.
A* uses the heuristics with cost function.
It applies the BFS and see the cost of every node and calculate the distance(i.e. heuristics function.)
complexity id O(n)
for BFS or DFS complexity is O(m+n)

- shashank.normative April 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use A* algo solve this problem.
A* uses the heuristics with cost function.
It applies the BFS and see the cost of every node and calculate the distance(i.e. heuristics function.)
complexity id O(n)
for BFS or DFS complexity is O(m+n)

- shashank.normative April 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bidirectional search will be better solution than others (A* or DFS) ...you can verify it using number of node visited by applying each search algorithm individually..

- tutum July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple DFS implementation.

public static void main(String[] args) {
    char[][] mat = {
            {'.', '.', '.', '.', 'W', 'X'},
            {'.', '.', 'W', '.', 'W', '.'},
            {'.', '.', 'W', '.', '.', '.'},
            {'.', '.', 'W', 'W', 'W', '.'},
            {'.', 'O', '.', '.', 'W', '.'},
            {'.', '.', '.', '.', '.', '.'}
    };
    assert existsPath(mat);
}

static class Pos {
    int r, c;

    Pos(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

private static boolean existsPath(char[][] mat) {
    int rows = mat.length;
    if (rows == 0) {
        return false;
    }
    int cols = mat[0].length;

    Pos start = find(mat, 'O', rows, cols);
    Pos end = find(mat, 'X', rows, cols);
    if (start == null || end == null) {
        return false;
    }

    Set<Integer> visited = new HashSet<>();
    return exists(start, end, visited, mat, rows, cols);
}

private static boolean exists(Pos curr, Pos end, Set<Integer> visited, char[][] mat, int rows, int cols) {
    if (curr.r < 0 || curr.r >= rows || curr.c < 0 || curr.c >= cols) {
        return false;
    }
    if (curr.r == end.r && curr.c == end.c) {
        return true;
    }
    final int pos = curr.r * cols + curr.c;
    if (visited.contains(pos)) {
        return false;
    }
    if (mat[curr.r][curr.c] == 'W') {
        return false;
    }


    visited.add(pos);
    if (exists(new Pos(curr.r - 1, curr.c), end, visited, mat, rows, cols) ||
            exists(new Pos(curr.r + 1, curr.c), end, visited, mat, rows, cols) ||
            exists(new Pos(curr.r, curr.c - 1), end, visited, mat, rows, cols) ||
            exists(new Pos(curr.r, curr.c + 1), end, visited, mat, rows, cols)) {
        return true;
    }
    visited.remove(pos);
    return false;
}

private static Pos find(char[][] mat, char ch, int rows, int cols) {
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (mat[r][c] == ch) {
                return new Pos(r, c);
            }
        }
    }
    return null;
}

- Safi December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is the code using backtracking. I have not bothered for boundary cases, but they can be incorporated as well. Following give some idea.

#include <iostream>
#include <set>

using namespace std;

template<typename T, typename U>
class Point
{
	public:
		Point(T x, U y);	
		bool operator== (const Point& other) const;
		bool operator!= (const Point& other) const;
		bool operator< (const Point& other) const;
		bool operator<= (const Point& other) const;
		bool operator>= (const Point& other) const;

		T m_x;
		U m_y;
};

template<typename T, typename U>
Point<T, U>::Point(T x, U y)
	: m_x(x),
	  m_y(y)
	{}

template<typename T, typename U>
bool Point<T, U>::operator== (const Point& other) const
{
	return m_x == other.m_x && m_y == other.m_y;
}

template<typename T, typename U>
bool Point<T, U>::operator!= (const Point& other) const
{
	return !(*this == other);
}

template<typename T, typename U>
bool Point<T, U>::operator< (const Point& other) const
{
	if (m_x < other.m_x) return true;
	else if (m_x == other.m_x)
		return m_y < other.m_y;
	else return false;
}

template<typename T, typename U>
bool Point<T, U>::operator<= (const Point& other) const
{
	return (*this < other) || (*this == other);
}


template<typename T, typename U>
bool Point<T, U>::operator>= (const Point& other) const
{
	return !(*this < other) || (*this == other);
}

template<typename T, typename U>
static bool PathExists(const Point<T, U>& o, const Point<T, U>& x, const set< Point<T, U> >& w,
					   set< Point<T, U> >& checked,
					   T tRange[2],
					   U uRange[2],
					   T tUnit,
					   U uUnit)
{
	if (o == x) return true;
	if (w.find(o) != w.end())  return false;
	
	bool checkPath = true;
	if ((o.m_x - tUnit) >= tRange[0])
	{
		Point<T, U> newO(o.m_x - tUnit, o.m_y);
		if (checked.find(newO) == checked.end())
		{
			checked.insert(newO);
			checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
			if (checkPath) return true;
		}
	}
	
	if ((o.m_x + tUnit) <= tRange[1])
	{
		Point<T, U> newO(o.m_x + tUnit, o.m_y);
		if (checked.find(newO) == checked.end())
		{
			checked.insert(newO);
			checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
			if (checkPath) return true;
		}
	}
	
	if ((o.m_y - uUnit) >= uRange[0])
	{
		Point<T, U> newO(o.m_x, o.m_y - uUnit);
		if (checked.find(newO) == checked.end())
		{
			checked.insert(newO);
			checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
			if (checkPath) return true;
		}
	}
	
	if ((o.m_y + uUnit) <= uRange[1])
	{
		Point<T, U> newO(o.m_x, o.m_y + uUnit);
		if (checked.find(newO) == checked.end())
		{
			checked.insert(newO);
			checkPath = PathExists(newO, x, w, checked, tRange, uRange, tUnit, uUnit);
			if (checkPath) return true;
		}
	}

	return false;
}

int main()
{
	int range[] = { 1, 7 };
	Point<int, int> start(1, 1);
	Point<int, int> end(7, 7);
	
	set< Point<int, int> > ws;
	
	ws.insert(*(new Point<int, int>(1, 2)));
	ws.insert(*(new Point<int, int>(2, 2)));
	ws.insert(*(new Point<int, int>(2, 3)));
	ws.insert(*(new Point<int, int>(2, 4)));
	ws.insert(*(new Point<int, int>(3, 5)));
	ws.insert(*(new Point<int, int>(4, 1)));
	ws.insert(*(new Point<int, int>(4, 5)));
	ws.insert(*(new Point<int, int>(4, 6)));
	ws.insert(*(new Point<int, int>(4, 7)));
	ws.insert(*(new Point<int, int>(5, 1)));
	ws.insert(*(new Point<int, int>(5, 3)));
	ws.insert(*(new Point<int, int>(5, 4)));
	ws.insert(*(new Point<int, int>(6, 1)));
	ws.insert(*(new Point<int, int>(6, 6)));
	ws.insert(*(new Point<int, int>(7, 2)));
	ws.insert(*(new Point<int, int>(7, 3)));
	ws.insert(*(new Point<int, int>(7, 4)));
	ws.insert(*(new Point<int, int>(7, 5)));
	
	set< Point<int, int> > checked;
	checked.insert(start);
	
	if (PathExists(start, end, ws, checked, range, range, 1, 1))
	{
		cout << "YaY, Found!" << endl;
	}
	else
	{
		cout << "Not found :(" << endl;
	}
	
	return 0;
}

- gimli April 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.io.*;

public class OtoX{
public static int rowfinal;
public static int colfinal;
public static int rowdir;
public static int coldir;
public static String[][] arr;
public static int rows;
public static int columns;

public static void main(String[] args){

try
{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

int row=0;
int col=0;
String input=reader.readLine();
String[] size=input.split(",");
rows=Integer.parseInt(size[0]);
columns=Integer.parseInt(size[1]);
arr=new String[rows][columns];

for(int i=0;i<rows;i++)
{
System.out.print("Enter row -"+i);
for(int j=0;j<rows;j++)
{
arr[i][j]=reader.readLine();
}
}
System.out.println("--------");
for(int i=0;i<rows;i++)
{
for(int j=0;j<rows;j++)
{
System.out.print(arr[i][j]);
if(arr[i][j].equals("O"))
{
row=i;
col=j;
}
else if(arr[i][j].equals("X"))
{
rowfinal=i;
colfinal=j;
}
}
System.out.println("");
}

if(rowfinal>row){
rowdir=1;
}
else{
rowdir=-1;
}

if(colfinal>col){
coldir=1;
}
else{
coldir=-1;
}
boolean result;

System.out.println(move(row,col,row,col));

}
catch(IOException e){
e.printStackTrace();

}

}

public static boolean move(int row,int col,int prevrow,int prevcol){
int nr;
int nc;
boolean result=false;
if(row==rowfinal && col==colfinal)
{
return true;
}
else
{
nr=row+rowdir;
nc=col;
//System.out.println(""+nr+"-"+nc);
if((nr)>-1 && nr < rows && (nr) !=prevrow && !arr[nr][nc].equals("W"))
{
arr[nr][nc]="W";
System.out.println("Trying to move to"+(nr)+","+nc);
result=move(nr,nc,row,col);
}
nr=row;
nc=col+coldir;

if((nc)>-1 && nc < columns && (nc) !=prevcol && !arr[nr][nc].equals("W") )
{
arr[nr][nc]="W";
System.out.println("Trying to move to"+(nr)+","+(nc));
result=move(nr,nc,row,col);
}
nr=row+rowdir*(-1);
nc=col;
// System.out.println(""+nr+"-"+nc);
if((nr)>-1 && nr < rows && (nr) !=prevrow && !arr[nr][nc].equals("W"))
{
arr[nr][nc]="W";
System.out.println("Trying to move to"+(nr)+","+nc);
result=move(nr,nc,row,col);
}
nr=row;
nc=col+coldir*(-1);
if((nc)>-1 && nc < columns && (nc) !=prevcol && !arr[nr][nc].equals("W") )
{
arr[nr][nc]="W";
System.out.println("Trying to move to"+(nr)+","+(nc));
result=move(nr,nc,row,col);
}
return result;
}



}

}

- ASEEM May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How does this look...too much memory?

import java.io.*;
import java.util.*;
import java.net.*;
import java.util.LinkedList;
import java.util.Queue;

public class Test
{
class Point
{
public int x, y;
public Point (int _x, int _y) { x = _x; y = _y; }
}

public boolean run()
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int rows;
int cols;
char[][] matrix;
Point start = null, end = null, p;

Queue<Point> q = new LinkedList<Point>();

try {
// read input file
String input = reader.readLine();
String[] size = input.split(",");

rows = Integer.parseInt(size[0]);
cols = Integer.parseInt(size[1]);
matrix = new char[rows][cols];

System.out.println(rows + " , " + cols);
for (int i = 0; i < rows; i++)
{
input = reader.readLine();
size = input.split(" ");
for (int j = 0; j < cols; j++)
{
matrix[i][j] = size[j].charAt(0);
if (matrix[i][j] == 'O') start = new Point(i,j);
if (matrix[i][j] == 'X') end = new Point(i,j);
System.out.print(" " + matrix[i][j]);
}
System.out.println("");
}

// search for path
q.add(start);
while ((p = q.poll()) != null)
{
matrix[p.x][p.y] = 'v'; // change from '.' to 'v' to indicate we visited this guy
if (p.x - 1 > -1) // north
{
if (matrix[p.x-1][p.y] == 'X') return true;
if (matrix[p.x-1][p.y] == '.')
q.add(new Point(p.x-1,p.y));
}
if (p.x + 1 < rows) // south
{
if (matrix[p.x+1][p.y] == 'X') return true;
if (matrix[p.x+1][p.y] == '.')
q.add(new Point(p.x+1,p.y));
}
if (p.y - 1 > -1) // west
{
if (matrix[p.x][p.y-1] == 'X') return true;
if (matrix[p.x][p.y-1] == '.')
q.add(new Point(p.x,p.y-1));
}
if (p.y + 1 < cols) // east
{
if (matrix[p.x][p.y+1] == 'X') return true;
if (matrix[p.x][p.y+1] == '.')
q.add(new Point(p.x,p.y+1));
}
}
}
catch (Exception e) {
e.printStackTrace();
}
return false;
}

public static void main(String[] args)
{
Test t = new Test();
boolean rc = t.run();
System.out.println("Result of test is " + rc);
}
}

- Anonymous June 02, 2012 | 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