## Facebook Interview Question for Front-end Software Engineers

Country: United States
Interview Type: Written Test

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

There is O(1) Solution

if(n==1 || m==1) {
cout<<(n+m-1) ;
}
else if((n%2)&&(m%2)) {
cout<<(n*m);
}
else if(n%2) {
cout<<((n*m)-((n-2)*(m-2)));
}
else {
cout<<(n*2);
}

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

@Anonymous
Agree! But I guess you need to explain it a little bit...

Ok, the point is that, first assume n>=2 and m>=2, in this case you can convince yourself that the Alex has no difficulty moving to the bottom of the table, but
1) He can continue doing similar movement to the right if n is odd.
2) He is stuck at the bottom-left corner if n is even.
In case 2) the tiles he cover is 2*n; in case 1) he can move all the way to the right, then he is facing the situation just like before: 3) if m is odd he can continue to move upwards, 4) otherwise he is stuck in the bottom-right corner.
In case 3) the problem actually reduces to a smaller size problem if you rotate the board by 180 degrees, and Alex eventually can travel anywhere on the board.
In case 4) the number of tiles he travel is 2*n + 2*(m-2).

Finally, you need to take care the boundary cases when n==1 or m==1, which is not hard (see Anonymous' solution above).

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

In this question, shouldn't the problem description be :
While moving forward, if he would go out of the table or reach a visited cell, he turns to his LEFT (instead of right as you have written).

Also, how do you explain him continuing from cell visited at 18 to the cell visited at 19. It is neither left nor right.

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

Your code does not satisfy the given test cases

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

the question is correct your solution is wrong

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

// You messed up on the order of case analysis

if(n==1 || m==1) {
cout<<(n+m-1) ;
}
else if((n%2)&&(m%2)) {
cout<<(n*m);
}
else if(m%2) {
cout<<(n*2);
}
else {
cout<<((n*m)-((n-2)*(m-2)));

}

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

good solution, 1 mistake though, in 2nd elseif it should be
elseif (m%2) then (n*m)-((n-2)*(m-2)), same problem with above solution as well

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

n =. rows, m =columns so

if only m even then n*2 + (m-2)*2 => (n*m)-((n-2)*(m-2)
if only n even then n*2

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

import java.awt.Point;
import java.io.*;
import java.util.*;

public class WalkingTable {

public static void main(String[] args) {
InputStream in = System.in;
Scanner scanner = new Scanner(in);
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
String[] split = line.split(" ");
int rows = Integer.parseInt(split[0]);
int cols = Integer.parseInt(split[1]);
solve(rows, cols);
}
scanner.close();
}

static void solve(int rows, int cols) {
Point pos = new Point(0, 0);
int dirIndex = 0;
Point[] directions = new Point[] { new Point(1, 0), new Point(0, 1),
new Point(-1, 0), new Point(0, -1) };
boolean[][] table = new boolean[rows][cols];
int moves = 0;
while (true) {
table[pos.y][pos.x] = true;
++moves;
Point direction = directions[dirIndex];
int attempts = 0;
while (attempts < 5 && !canMove(table, pos, direction)) {
dirIndex += 1;
dirIndex %= directions.length;
direction = directions[dirIndex];
++attempts;
}
if (!canMove(table, pos, direction)) {
break;
} else {
pos.translate(direction.x, direction.y);
}
dirIndex++;
dirIndex %= directions.length;
}
System.out.println(moves);
}

static boolean canMove(boolean[][] table, Point pos, Point moveDir) {
int x = pos.x + moveDir.x;
int y = pos.y + moveDir.y;
if (x < 0 || y < 0 || y >= table.length || x >= table[0].length || table[y][x]) {
return false;
}
return true;
}
}

I didn't notice the O(1) solution. My solution's time and space complexity is O(n^2). I'm simulating the problem.

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

Can be improved but will do it. Ruby implementation

class Turtle

def initialize(n,m)

return nil if n.nil? or m.nil?

if n < 1 or m < 1
end

@n = n
@m = m
@pos_x = 0
@pos_y = 0
@dir_index = 0
@moves = 0
@cells_visited = Array.new
@directions = [:east,:south,:west,:north]

end

attr_accessor :n,:m,:moves,:pos_x,:pos_y,:cells_visited,:directions,:dir_index

def move_forward

@pos_x += 1 if @directions[@dir_index] == :east
@pos_x -= 1 if @directions[@dir_index] == :west
@pos_y -= 1 if @directions[@dir_index] == :north
@pos_y += 1 if @directions[@dir_index] == :south

end

def move_backwards

@pos_x -= 1 if @directions[@dir_index] == :east
@pos_x += 1 if @directions[@dir_index] == :west
@pos_y += 1 if @directions[@dir_index] == :north
@pos_y -= 1 if @directions[@dir_index] == :south

end

def turn_right

if @dir_index == 3
@dir_index = 0
else
@dir_index += 1
end

end

def visited?

val = @cells_visited.select { |x| x == [@pos_x,@pos_y] }

val.empty? ? false : true

end

def validate_move_forward

move_forward
if @pos_x != n and @pos_y != m and not visited? and @pos_x >= 0 and @pos_y >= 0
move_backwards
return true
else
move_backwards
return false
end

end

@cells_visited.push([pos_x,pos_y])

end

def count

max_fails = 4
fails_count = 0
while fails_count != max_fails
puts "DEBUG: #{@pos_x} #{@pos_y} #{@directions[@dir_index]} #{@validate_move_forward}"
if validate_move_forward
@moves += 1
move_forward
turn_right
fails_count = 0
else
turn_right
fails_count += 1
end
end

return @moves + 1

end

end

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

dir 1 represents right dir 2 represents down dir 3 represents left and dir 4 represents up

#include<iostream>
using namespace std;
int ch[101][101],n,m,ans;
int dfs(int i,int j,int dir,int k)
{
if(ch[i][j] || i>=n || i<0 || j<0 || j>=m) return 0;
ch[i][j]=k;
if(dir==0)
{
if(dfs(i,j+1,1,k+1))return 1;
if(dfs(i+1,j,2,k+1))return 1;
if(dfs(i,j-1,3,k+1))return 1;
if(dfs(i-1,j,4,k+1))return 1;
}
if(dir==4)
{
if(dfs(i,j+1,1,k+1))return 1;
if(dfs(i+1,j,2,k+1))return 1;
if(dfs(i,j-1,3,k+1))return 1;
if(dfs(i-1,j,4,k+1))return 1;
}
if(dir==1)
{
if(dfs(i+1,j,2,k+1))return 1;
if(dfs(i,j-1,3,k+1))return 1;
if(dfs(i-1,j,4,k+1))return 1;
if(dfs(i,j+1,1,k+1))return 1;
}
if(dir==2)
{
if(dfs(i,j-1,3,k+1))return 1;
if(dfs(i-1,j,4,k+1))return 1;
if(dfs(i,j+1,1,k+1))return 1;
if(dfs(i+1,j,2,k+1))return 1;
}
if(dir==3)
{
if(dfs(i-1,j,4,k+1))return 1;
if(dfs(i,j+1,1,k+1))return 1;
if(dfs(i+1,j,2,k+1))return 1;
if(dfs(i,j-1,3,k+1))return 1;
}
return 1;
}
int main()
{
cin>>n>>m;
dfs(0,0,0,1);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
ans=max(ans,ch[i][j]);
}
}
cout<<ans<<endl;
cin>>n>>m;
}

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

if n and m are neither even nor 1 then will the answer be n*m?

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

#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int n,m,ans;
scanf("%d %d",&n,&m);
if(n%2==0)
ans=2*n;
else
if(m%2==0)
ans=2*n+2*(m-2);
else
ans=n*m;
printf("%d",ans);
return 0;
}

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

#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int n,m,ans;
scanf("%d %d",&n,&m);
if(n%2==0)
ans=2*n;
else
if(m%2==0)
ans=2*n+2*(m-2);
else
ans=n*m;
printf("%d",ans);
return 0;

}

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

Working fast code using backtracking

#include <iostream>
using namespace std;

int n=0,m=0;
int ** visited = NULL;
static int stepcount = 1;
int dircount=1;
int i=0;
int j=0;

bool isAllowed( int p ,int q)
{
if( p>=0 && p<n && q>=0 && q<m && visited[p][q]==0)
return true;
else
return false;
}

bool setdirection()
{
int oldi = i;
int oldj = j;
switch(dircount%4)
{
case 1: j = j+1;break;				//right
case 2: i = i+1;break;				// down
case 3: j = j-1;break;				// left
case 0: i = i-1; break;			//  top
}
dircount++;
bool test = isAllowed(i,j);
if(test == false)
{
i = oldi;
j = oldj;
}
return test;
}

void traverse ()
{
bool flag= true;
int t = 0;

while(setdirection() == false)
{
t++;
if(t==5)
{
flag = false;
break;
}
}

if(flag == true)
{
// cout<<"Visited Array("<<(i)<<" , "<<(j)<<" )"<<endl;
visited[i][j] = true;
stepcount++;
traverse();
}
else
{
cout<<"\nPrint stepcount"<<stepcount<<endl;
}
}

int main()
{
cin>>n>>m;
int * pt = NULL;
visited = new int* [n*sizeof(pt)];

// allocating and intializing array
for(int i=0;i<n;i++)
{
visited[i] = new int[m*sizeof(pt)];
}

for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
visited[i][j] = 0;
}
}

visited[0][0] = 1;
traverse();

// freeing memory
for(int i=0;i<n;i++)
{
delete [] visited[i];
}
delete [] visited;
system("pause");
return 0;
}

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

#include <iostream>
using namespace std;

int i = 0 ;
int j = 0 ;
int* ptr_i = &i ;
int* ptr_j = &j ;

enum dir{ r = 1 , down , l , up } ;

dir lastdir = up ;

bool visited( int* board , int i , int j , int n , int m )
{
if( board[ i*m+j ] == 1 )
return true ;
else
return false ;
}

bool moveOneStep( int* board , int *ptr_i , int* ptr_j , int n , int m )
{
int temp_i = *ptr_i ;
int temp_j = *ptr_j ;

if( lastdir == up )
{
cout << temp_i << " " << temp_j << endl ;
if( !visited( board , temp_i , temp_j+1 ,n,m ) && (temp_j+1) != m )
{
board[ temp_i*m + temp_j+1 ] = 1 ;
*ptr_j = *ptr_j + 1 ;
lastdir = r ;
return true ;
}
else if( !visited( board , temp_i , temp_j-1 ,n,m ) && (temp_j-1) != -1 )
{
board[(temp_i)*m + (temp_j-1)] ;
*ptr_j = *ptr_j-1 ;
lastdir = l ;
return true ;
}
else if( !visited( board , temp_i-1 , temp_j,n,m ) && (temp_i-1) != -1 )
{
board[ (temp_i-1)*m + temp_j ] = 1 ;
*ptr_i = *ptr_i -1 ;
lastdir = up ;
return true ;
}
else
return false ;
}
else if( lastdir == r )
{
cout << temp_i << " " << temp_j << endl ;
if( !visited( board , temp_i+1 , temp_j,n,m ) && (temp_i+1) != n )
{
board[(temp_i+1)*m + temp_j ] = 1 ;
*ptr_i = *ptr_i + 1 ;
lastdir = down ;
return true ;
}
else if( !visited( board , temp_i-1 , temp_j ,n,m ) && (temp_i-1) != -1 )
{
board[ (temp_i-1)*m + (temp_j) ] = 1;
*ptr_i = *ptr_i-1 ;
lastdir = up ;
return true ;
}
else if( !visited( board , temp_i , temp_j+1 , n,m) && (temp_j+1) != m )
{
board[ (temp_i)*m + temp_j+1 ] = 1 ;
*ptr_j = *ptr_j+1 ;
lastdir = r ;
return true ;
}
else
return false ;
}
else if( lastdir == down )
{
cout << temp_i << " " << temp_j << endl ;
if( !visited( board , temp_i , temp_j-1,n,m) && (temp_j-1) != -1 )
{
board[(temp_i)*m + (temp_j-1)] = 1;
*ptr_j = *ptr_j-1 ;
lastdir = l ;
return true ;
}
else if( !visited( board , temp_i , temp_j+1,n,m ) && (temp_j+1) != m )
{
board[temp_i*m + temp_j+1 ] = 1 ;
*ptr_j = *ptr_j + 1 ;
lastdir = r ;
return true ;
}
else if( !visited( board , temp_i+1 , temp_j,n,m) && (temp_i+1) != n )
{
board[ (temp_i+1)*m + temp_j ] = 1 ;
*ptr_i = *ptr_i+1 ;
lastdir = down ;
return true ;
}
else
return false ;
}
else if( lastdir == l )

{
cout << temp_i << " " << temp_j << endl ;
if( !visited( board , temp_i+1 , temp_j , n,m ) && (temp_i+1) != n )
{
board[(temp_i+1)*m + temp_j ] = 1 ;
*ptr_i = *ptr_i + 1 ;
lastdir = down ;
return true ;
}
else if( !visited( board , temp_i-1 , temp_j,n,m) && (temp_i-1) != -1 )
{
board[(temp_i-1)*m + (temp_j)] = 1 ;
*ptr_i = *ptr_i-1 ;
lastdir = up ;
return true ;
}
else if( !visited( board , temp_i , temp_j-1,n,m) && (temp_j-1) != -1 )
{
board[ (temp_i)*m + temp_j-1 ] = 1 ;
*ptr_j = *ptr_j-1 ;
lastdir = l ;
return true ;
}
else
return false ;
}
}

int main() {
int n ;
int m ;
cin >> n >> m ;
int *board = new int[n*m] ;

for( int i = 0 ; i<n ; i++ )
{
for ( int j = 0 ; j<m ; j++)
board[i*m+j] = 0 ;

}

board[0] = 1 ;
int steps = 1 ;
int i = 0 ;
int j = 0 ;

cout << endl ;

while( moveOneStep( board , &i , &j , n , m ) )
steps++ ;

cout << steps << endl ;

for( int i = 0 ; i<n ; i++ )
{
for ( int j = 0 ; j<m ; j++)
cout << board[i*m+j] ;
cout << endl ;
}
return 0;
}

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

Here is the implementation in Java, complexity in O(n*m)

public class Count {

public static void main(String[] args) {
int n = 9;
int m = 9;
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = 0;
}
}
System.out.println("Total moves:" + countMoves(grid, n, m));
}

public static int countMoves(int[][] grid, int row, int col) {
int count = 0;
int x = 0;
int y = 0;
char direction = 'r';
int[][] trace = new int[row][col];
while ((direction = deadlock(grid, x, y, direction, row, col)) != 'x') {
count++;
grid[x][y] = 1;
trace[x][y] = count;
switch (direction) {
case 'r':
y++;
direction = 'd';
break;
case 'l':
y--;
direction = 'u';
break;
case 'u':
x--;
direction = 'r';
break;
case 'd':
x++;
direction = 'l';
break;
default:
break;
}
}
printMatrix(trace, row, col);
return count;
}

public static char deadlock(int[][] grid, int x, int y, char direction,
int row, int col) {
switch (direction) {
case 'r':
if (canMove(grid, x, y, 'r', row, col)) {
return 'r';
} else if (canMove(grid, x, y, 'd', row, col)) {
return 'd';
} else if (canMove(grid, x, y, 'l', row, col)) {
return 'l';
} else if (canMove(grid, x, y, 'u', row, col)) {
return 'u';
} else {
return 'x';
}
case 'l':
if (canMove(grid, x, y, 'l', row, col)) {
return 'l';
} else if (canMove(grid, x, y, 'u', row, col)) {
return 'u';
} else if (canMove(grid, x, y, 'r', row, col)) {
return 'r';
} else if (canMove(grid, x, y, 'd', row, col)) {
return 'd';
} else {
return 'x';
}
case 'u':
if (canMove(grid, x, y, 'u', row, col)) {
return 'u';
} else if (canMove(grid, x, y, 'r', row, col)) {
return 'r';
} else if (canMove(grid, x, y, 'd', row, col)) {
return 'd';
} else if (canMove(grid, x, y, 'l', row, col)) {
return 'l';
} else {
return 'x';
}
case 'd':
if (canMove(grid, x, y, 'd', row, col)) {
return 'd';
} else if (canMove(grid, x, y, 'l', row, col)) {
return 'l';
} else if (canMove(grid, x, y, 'u', row, col)) {
return 'u';
} else if (canMove(grid, x, y, 'r', row, col)) {
return 'r';
} else {
return 'x';
}
default:
return 'x';
}

}

public static void printMatrix(int[][] a, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println("");
}
}

public static boolean canMove(int[][] grid, int x, int y, char direction,
int row, int col) {
switch (direction) {

case 'r':
if ( y + 1 < col && grid[x][y + 1] == 0) {
return true;
} else {
return false;
}
case 'l':
if (y - 1 >= 0 && grid[x][y - 1] == 0) {
return true;
} else {
return false;
}
case 'u':
if (x - 1 >= 0 && grid[x - 1][y] == 0) {
return true;
} else {
return false;
}
case 'd':
if (x + 1 < row && grid[x + 1][y] == 0) {
return true;
} else {
return false;
}
default:
break;
}
return false;

}

}

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

PHP code Here

\$leer = fopen("php://stdin", "r");
\$escribir = fopen("php://stdout", "w");

fscanf(\$leer, "%d", \$n);
fscanf(\$leer, "%d", \$m);

if(\$n == 1 || \$m == 1)
{
\$resultado = \$n + \$m - 1;
}
else if((\$n % 2) && (\$m % 2))
{
}
else if(\$n % 2)
{
\$resultado = ( (\$n * \$m) - ((\$n - 2) * (\$m - 2)) );
}
else
{
}

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

There is a recurrence relation for f of the form

f(m,n) = 2n // if m is even
else f(m,n) = 2n + f(n-2,m)

// base cases
f(1,n) = n, f(m,1) = m

eg) f(7,4) = 14 + f(2,7)
= 14 + 4 = 18

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

function createGrid(M, N) {
var grid = new Array(M).fill(false);
var i;
for (i = 0; i < M; i++) {
grid[i] = new Array(N).fill(false);
};
return grid;
}

function canMoveUp(grid, x, y) {
return x > 0 && !grid[x-1][y];
}

function canMoveDown(grid, x, y) {
return x + 1 < grid.length && !grid[x+1][y];
}

function canMoveLeft(grid, x, y) {
return y > 0 && !grid[x][y-1];
}

function canMoveRight(grid, x, y) {
return y + 1 < grid[x].length && !grid[x][y+1];
}

function canMove(grid, x, y) {
return canMoveLeft(grid, x, y) ||
canMoveRight(grid, x, y) ||
canMoveUp(grid, x, y) ||
canMoveDown(grid, x, y);
}

function AlexMoves(row, col) {
var grid = createGrid(row, col);
var x = 0, y = 0, moves = 0;
grid[x][y] = true;

while (canMove(grid, x, y) && moves < row*col) {
if (canMoveRight(grid, x, y)) {
// console.log('move right');
grid[x][y+1] = true;
y += 1;
moves++;
}
if (canMoveDown(grid, x, y)){
// console.log('move down');
grid[x+1][y] = true;
x += 1;
moves++;
}
if (canMoveLeft(grid, x, y)) {
// console.log('move left');
grid[x][y-1] = true;
y -= 1;
moves++;
}
if (canMoveUp(grid, x, y)) {
// console.log('move up');
grid[x-1][y] = true;
x -= 1;
moves++;
}
}

return moves;
}

console.log(AlexMoves(5, 6)); // 17
console.log(AlexMoves(3, 4)); // 10
console.log(AlexMoves(4, 4)); // 7

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

I wrote in JavaScript

const rotate = (function() {
let dir = -1;
return function(row, col) {
dir++;
if (dir === 4) dir = 0;
switch (dir) {
case 0: return [row, col+1];
case 1: return [row + 1, col];
case 2: return [row, col - 1];
case 3: return [row - 1, col];
}
}
})()

function spiralGo(row, col) {
const visited = ['0,0'];
let footprint = [];
for (let i = 0; i < row; i++) {
footprint.push([]);
}
let r = 0, c = 0, count = 1, times = 0;
footprint[r][c] = count++;
let nextStep;
while (times < 5) {
nextStep = rotate(r,c);
times++;
if (!visited.includes(nextStep.toString()) && nextStep[0] < row && nextStep[0] >= 0 && nextStep[1] < col && nextStep[1] >= 0) {
times = 0;
visited.push(nextStep.toString());
[r, c] = nextStep;
footprint[r][c] = count++;
}
}

return footprint;
}

console.log(spiralGo(9, 9));

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

This solution is O(mn).

private static class AlexState {
int rv = 0;
int cv = 0;
DIR dir = DIR.MINUS_R;

private enum DIR {
MINUS_R(0), PLUS_C(1), PLUS_R(2), MINUS_C(3);

private int val;

private DIR(int val) {
this.val = val;
}
}
}
public static void main(String[] args) {
int rc = 9, cc = 9;
boolean[][] cells = new boolean[rc][cc];
for (int i = 0; i < rc; i++) {
for (int j = 0; j < cc; j++) {
cells[i][j] = false;
}
}
AlexState state = new AlexState();
cells[0][0] = true;
System.out.println(findVisitedCellsCount(cells, rc, cc, state));
}

public static int findVisitedCellsCount(boolean[][] cells, int rc, int cc, AlexState s) {
int cnt = 0;
int vc = 1;
while (cnt < 4) {
cnt++;
switch (s.dir) {
case MINUS_R:
s.dir = AlexState.DIR.PLUS_C;
if (s.cv < cc - 1 && !cells[s.rv][s.cv + 1]) {
cnt = 0;
cells[s.rv][s.cv + 1] = true;
s.cv++;
vc++;
}
break;
case PLUS_C:
s.dir = AlexState.DIR.PLUS_R;
if (s.rv < rc - 1 && !cells[s.rv + 1][s.cv]) {
cnt = 0;
cells[s.rv + 1][s.cv] = true;
s.rv++;
vc++;
}
break;
case PLUS_R:
s.dir = AlexState.DIR.MINUS_C;
if (s.cv > 0 && !cells[s.rv][s.cv - 1]) {
cnt = 0;
cells[s.rv][s.cv - 1] = true;
s.cv--;
vc++;
}
break;
case MINUS_C:
s.dir = AlexState.DIR.MINUS_R;
if (s.rv > 0 && !cells[s.rv - 1][s.cv]) {
cnt = 0;
cells[s.rv - 1][s.cv] = true;
s.rv--;
vc++;
}
break;
}
}
return vc;
}

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

According to your code, the answer for the first sample test (3,3) is 6...

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.