## Facebook Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

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

Let us define a function is_first_player_winner() which returns 1 if the first player can control the game and force a win. This function returns 0 if the first player cannot do so, and consequently the second player wins.

Now, we can think of a recursive solution. If we want to find out if the first player can force a win for a given value if "N", we can consider all possible combinations of the first two moves.

We can divide N by the product of the first two moves and then apply the same function recursively to check if player 1 can force a win (Optimal substructure).

Based on the answer of these sub-problems, we can check if player 1 can force a win or not.

``````// Recursive Solution

int is_first_player_winner (int n)
{
/* Returns 1 if Player_1 can control and win the game
Returns 0 if the Player_1 cannot control and win the game */

if ( n <= 1 )
{
// should not reach here
// exit
}
if (n > 2 && n <= 9)
return 1;         // first player wins
if (n > 9 && n <= 18)
return 0;         // first player cannot win

/* Consider the first two moves in the game
They can be one of the following: (2,2), (2,9), (9,2), (9,9) */
// case 2,2
int win_2_2 = is_first_player_winner (ceil((float)n/4));

// case 2,9 or 9,2
int win_2_9 = is_first_player_winner (ceil((float)n/18));

// case 9,9
int win_9_9 = is_first_player_winner (ceil((float)n/81));

if ((win_2_2 && win_2_9) || (win_9_9 && win_2_9))
return 1;
else
return 0;
}``````

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

This comment has been deleted.

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

I mean go over. What do you mean by Else the better of (opposite of F(i+1, j)) and (opposite of F(i, j+1))?

Could you write codes using DP?

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

Is any player fixed for playing the first chance ?
suppose we could assume that P-1 always gets the first chance.

Is this question is about getting closer to N than the other player to win the game ?
please correct me if i am getting wrong interpretation of the question

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

``````#include<iostream>
using namespace std;
int playgame(int n,int turn,int x);
int main()
{
int x=playgame(0,0,1); // first argument is n, second is player's turn(0 for first 1 for second) , third is starting no to each player(1)
cout<<x;

return 0;
}
int playgame(int n,int turn,int x)
{
if(x*2>=n &&  x*9>=n)
return turn;

int l=playgame(n,(turn+1)%2,x*2);
int r=playgame(n,(turn+1)%2,x*9);
return (l || r);

}``````

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

BACKTRACK solution.

assumption:
player 0 play first

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

that's incorrect, if the n = 4, the return value will be 1, but it should be 0

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

if the n <= 9, the first player wins
if the 9 < n <= 18, the second player wins
if the 18 < n <= 36, the first player wins
if the 36 < n <= 72, the second player wins

conclusion :
find the least number a, when n <= 9 * 2^a, if a is even, the first player wins, if a is odd, the second player wins

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

Can you please prove its correctness ?

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

this approach is incorrect, the counter case is 162(9*2*9), 162 < 9 * 2^5, but first player will win.

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

cwj - you are right.. it depends on considering the fact that p1 and p2 are very intelligent and knows how to choose so as to not let other win (choose 2 to keep it less and once target is less than result*9 (choose 9 to win). or choose 2 9s.. its confusing me - i think we need a mathematician here! :)

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

input number is N, if there are n steps to finish this game,
the step n must multiply 9 to finish the game.
the step n-1 must multiply 2 to avoid to reach N/9 (when N/9 > 9, if N/9<9, game over).
the step n-2 must multiply 9 to reach the N/9/2 (when N/9/2 > 9, if N/9/2<9, game over).
...
finally, the remain number <=9, get the winner.

here is the code (not test)

boolean game(int N, int value, boolean flag)
{
if(N <= 9)
{
if(flag) return true;
return false;
}
else
{
int remain = (N%value == 0 ? N/value : N/value+1;
return game(remain, value == 9 ? 2 : 9, !flag);
}
}

// true : first win, false : second win
boolean game(int N)
{
return game(N, 9, true);
}

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

correction :

if(N <= 9)
{
if(flag) return true;
// flag is false
if(N == 3 || N == 4 || N == 9) return true;
return false;
}

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

here is more explain :
the winner will trigger the last step n, so it must be 9, because N/9 must appear earlier than N/2.then let's put the n-1 step aside, consider the n-2 step, that's also triggered by winner, he has two choices, make the number of N/9/2 or N/9/9, if he chose N/9/9, the loser can win by N/9/9 *2*2*2*2 to let the winner reach N/9 first.
so the winner must choose N/9/2 to force the loser reach the N/9 at step n-1. now the question come back, the winner must reach N/9/2 first, how? make the loser reach (N/9/2)/9 ...

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

Solution: If player 1 can make one successful combination of moves which is not broken by either choice by player 2 then he wins else player 2 wins. Dynamic programming might be useful although I am not sure how as in dynamic programming we are usually incrementing towards solution here it is other way around.

#include<iostream>
#include<conio.h>
using namespace std;
bool playgameplayer2(float n);
bool playgameplayer1(float n)
{
if(n<=9) {
return true;
}

bool l=playgameplayer2(n/2);
bool r=playgameplayer2(n/9);
return (l || r);

}
bool playgameplayer2(float n)
{
if(n<=9) {
return false;
}

bool l=playgameplayer1(n/2);
bool r=playgameplayer1(n/9);
return (l && r);

}
int main()
{
float n;
cin>>n;
bool x=playgameplayer1(n); // first argument is n, second is player's turn(0 for first 1 for second) , third is starting no to each player(1)
cout<<x;
getch();
return 0;
}

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

ignore the comment line in main.

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

``````#include<iostream>
#include<conio.h>
using namespace std;
bool playgameplayer2(float n);
bool playgameplayer1(float n)
{
if(n<=9) {
return true;
}

bool l=playgameplayer2(n/2);
bool r=playgameplayer2(n/9);
return (l || r);

}
bool playgameplayer2(float n)
{
if(n<=9) {
return false;
}

bool l=playgameplayer1(n/2);
bool r=playgameplayer1(n/9);
return (l && r);

}
int main()
{
float n;
cin>>n;
bool x=playgameplayer1(n); // first argument is n, second is player's turn(0 for first 1 for second) , third is starting no to each player(1)
cout<<x;
getch();
return 0;
}``````

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

Hi sd, can you explain why we n /2 instead of n - 2? Thanks.

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

they are multiplyin number....I am doing other way around

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

I've put some of my earlier comments into a complete solution:

Let F(i, j) be true if the winner of the game is the player whose turn it is next when we start at 2^i*9^j, false otherwise.

Then, since we start at 2^0*9^0 = 1 and with the first player's turn being next, we can write:

``boolean FirstPlayerIsWinner = F(0,0)``

Now, F(i, j) is automatically true if 2^i * 9^j * 9 >= N. That is, if there is some number the player can multiply by and immediately win.

If that's not the case, F(i, j) is true if and only if either of F(i+1, j) and F(i, j+1) is false. Why? The number is currently 2^i*9^j. F(i,j) represents whether the current player will win starting from this number. If the current player multiplies by 2, it will be the other player's turn and the number will be 2^(i+1)*9^j. So F(i+1, j) will represent whether the opposing player (whose turn it now is) will win. The same logic applies for 9: F(i, j+1) will represent whether the opposing player will win.

So if F(i+1, j) and F(i, j+1) are both true, the current player loses: no matter what, the opposing player will win. However, if at least one is false, the current player would pick that move, causing the opposing player to lose and giving the current player the victory. Therefore, in this case, we can write: F(i, j) = not (F(i+1, j) and F(i, j+1))

So the overall formula now is:

``````boolean FirstPlayerIsWinner = F(0,0)

F(i, j) =
If 2^i * 9^j * 9 >= N then true
Else not (F(i+1, j) and F(i, j+1))``````

So that sets up basic recursion. We will need dynamic programming to help us evaluate this efficiently. This is just a matter of setting up simple memorization. With the constraints given, we can see that i< 32 and j < about 10, so a dynamic programming solution will be plenty fast.

This entire solution assumes that we don't have to deal with overflows, etc.

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

How is this Dynamic Programming? You are looking at super-problems than sub-problems!

Trying to define F(i, j) in terms of F(i+1, j) and F(i, j+1)!

Please do correct me if I'm missing something.

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

Whether it's a sub-problem or a super-problem is a matter of perspective, I suppose. What counts is that if you draw a graph showing all the function calls, that graph is a DAG.

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

Yes you are right. It doesn't matter. your base case ensures solution.

actually, recently I tried this DIEHARD problem from spoj and tried to define problem in terms of super-problems but couldnt' find proper base-cases to support it.

www [DOT] spoj [DOT] pl/problems/DIEHARD/

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

Ok, so I'm assuming that the number has to be perfectly divisible by 2 or 9 or a combination of these for someone to win (so prime numbers are out for e.g.), in which case I think it's just a case of how many multiples of these are factors of the number in question, and if P1 goes first, then he can only win if there's an odd number of multiples:

``````public class Game2_9 {

public static void main(String[] args) {
System.out.println(new Game2_9().winner(24234234));
System.out.println(new Game2_9().winner(2*2*2*2*9*9*9*2));
System.out.println(new Game2_9().winner(2*2*2*2*9*9*9*2*9*2*2));
System.out.println(new Game2_9().winner(1));
}

public int winner(int N) {
int goes = calcGoes(N);
// for goes == 0, need to consider whether first player
// has to pick between 2 or 9, or whether can decide not to pick because it's 1
// i've assumed they have to pick, so nobody wins
if (goes == -1 || goes ==0) {
return 0;
}
if (goes%2==0) {
return 2;
}
return 1;
}

private int calcGoes(int n) {
if (n == 1) {
return 0;
}
if (n%9==0) {
int goes = calcGoes(n/9);
return goes==-1?-1:goes+1;
}
if (n%2==0) {
int goes = calcGoes(n/2);
return goes==-1?-1:goes+1;
}
return -1;
}
}``````

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

// turn = 0 player 1 wins
//turn = 1 player 2 wins
int Win(int N, int turn, int dice)
{
if(N == 0)
return turn
if(N < 0 )
return -1
else
{
Win(N - dice*2, !turn, dice+1);
Win(N - dice*9, !turn, dice+1);
}
}

Do let me know If I am making any mistake here

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

classic game-theory question, recursion would give the most concise solution..

``````def win( i, N ) :
if( i*9 >= N ) : return True
return not (win( i*2, N ) and win( i*9, N ))``````

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

this number N can only be represented as 2^k1*9^k2

if ((k1+k2)%2 == 1)
1 win
else
2 win

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

probably.... 0 for player 0, 1 for player 1, -1 for impossible cases like 13,17,19,..34,38..

``````int winner(int no)
{
if (no<=0) return -1;
if (no<=9) return 0;
int i;
for(i=2;i<=9;i++)
{
int j=winner(no/i);
if(!(no%i) && j!=-1){if(j==0) return 1;else return 0; }
}
return -1;
}``````

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.