Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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)
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;
}
. . . . . . .
. . . . . . .
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.
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;
}
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;
}
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;
}
}
}
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);
}
}
This can be solved by Simple Depth First Search using Recursion..
- Krish April 11, 2012