Facebook Interview Question Front-end Software Engineers
Country: United States
Interview Type: Written Test
@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).
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.
// 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)));
}
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
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.
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
raise "Failed bad arguments"
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
def add_visited
@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}"
add_visited
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
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;
}
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;
}
#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;
}
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;
}
}
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))
{
$resultado = $n * $m;
}
else if($n % 2)
{
$resultado = ( ($n * $m) - (($n - 2) * ($m - 2)) );
}
else
{
$resultado = $n * 2;
}
fprintf($escribir, "%d", $resultado);
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
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));
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;
}
There is O(1) Solution
- Anonymous August 01, 2013if(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); }