## Facebook Interview Question for Software Engineer / Developers

• 5

Country: United States
Interview Type: Written Test

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

The total number of rounds would be number of 0s before each 1 bit set in n. If n = 12 (1100). Then the player-1 selects k=1 to conserve the same number of 1s in the number. So, now n becomes 10(1010). Then player-2 selects k=0 and n becomes 9(1001). Then it continues to 5(0101)->3(0011). Total number of rounds is 4 which is number of zeroes before each 1 bit set in n. If you further look to conserve the property of equal number of 1s the player will select a k such that it is the first zero that has next higher bit set to 1. Here is the code in action:

``````public int selectWinner (int n) {

int total = 0;
int numZeros = 0;

while (n!=0) {
if (n&0x01) {
total +=numZeros;
} else {
numZeros++;
}
n=n>>1;
}
return (total%2)?2:1;
}``````

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

Is'nt there a better than O(n) way to do this??

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

1100->1010->1001->0101->0011

why will this not happen
1100->1010->1001->0111
why will one player play it badly its written it has to be as beautiful as previous

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

It says "The beauty of a number depends on the number of one's in its binary representation" so 1001->0111 is not a valid move.

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

You can optimize it a touch further by initially checking a base case:
if (!(n & (n+1)))
return 2; //if n is 1 less than a power of 2 then binary is all 1s and player 1 is screwed

if n is a power of 2 then total would just be logbase2 of n but it's not worth adding this check.

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

For the input n, in binary format "100101", the first player, A will lose the game, and the second player B, will win. BC, A can change n to "100011" or "10101", at the first round. For "100011", B can easily win the game. For "10101", B can win the game by change it to "10011".
We can change the model of this problem to the following. Considering there are several buckets, in each of them, there are some balls (means the number of '0'), or, nothing. For instance, "100101" can be represented by 2 buckets, the first bucket has 2 balls and second has 1. Then, for each player, he can pick one bucket and move one ball from the this bucket (ith one) to the (i - 1)th bucket. Of cause, we can only move the ball forward. The guy that moves the last ball win the game.

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

CODE:

``````int willFirstWin(int result[], int len) {
int i = 1;
while (i < len) {
if (result[i] > 0)
break;
i++;
}
if (i == len)
return -1;

for (i = 1; i < len; i++) {
if (result[i] == 0)
continue;
result[i - 1]++;
result[i]--;
if (willFirstWin(result, len))
return 0;
}
return -1;
}``````

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

@went, you forgot the reset result array after the recursion. NICE solution though!

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

``````int willFirstWin(int result[], int len) {
int i = 1;
while (i < len) {
if (result[i] > 0)
break;
i++;
}
if (i == len)
return -1;

for (i = 1; i < len; i++) {
if (result[i] == 0)
continue;
result[i - 1]++;
result[i]--;
if (willFirstWin(result, len))
return 0;
result[i - 1]--;
result[i]++;
}
return -1;
}``````

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

B can win the game by change it to "10011".
if B change it to 10011 A can then change it to 1111 where B actually loses

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

@ kkr.ashish, " the number n-2^k has to be as beautiful as n", therefore, A cannot change "10011" to "1111"

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

B can win the game by change it to "10011".
if B change it to 10011 A can then change it to 1011, which is as beautiful as 10011?

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

B changes to 10011
A changes to 01011
B changes to 00111 ---> Now B wins.

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

Both players play optimally. Hence if B changes to 10011, then A changes to 00111 and A wins

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

@keinnnn
@ kkr.ashish, " the number n-2^k has to be as beautiful as n", therefore, A cannot change "10011" to "1111"

1111 has 4 1's
and 10011 has 3 1's
so 1111 is more beautiful than 10011
so holds good
correct me if i am wrong

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

@Miguel Oliveira
"Both players play optimally. Hence if B changes to 10011, then A changes to 00111 and A wins" How can you change 10011 to 00111 by doing 100111 - 2^k
??

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

you're right. it had been a while since i first read the problem and forgot about that

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

@kkr.ashish:
"the number n-2^k has to be as beautiful as n", which mean, we need to have the same number of 1s is n and n-2^k , which means, we cannot change 10011 to 1111, because they have different number of 1s. Therefore, if B change the number to 10011, the only choice for A for the next step is to change it to 1011, and B will change it to 111. At the end, B won!

What's more, how can you get the conclusion that "so 1111 is more beautiful than 10011"?

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

ok my bad .. i assumed the number should be atleast as beautiful.. seems the question seemed to be about equal to

for the given question it seems odd as there is not much choice for the players to make wise decisions the moves are very much forced nothing much they can do
as you can see in the test case you mentioned both return to 10011 state

say for 100110011
there will be total 2+ 3*2 moves possible the ordering can be different but it will be 8 moves
100110011 - > 10110011->1110011->1101011->1011011->111011->110111
->101111->111111
so i assume for 1001100110011
the output will be 2+ 2*3+2*5 = 18 moves
so this looks pretty much fixed if the beauty is preserved

100101 - > 2+ 1*2 = 4 moves so A loses
10101 - > 1+ 2*1 =3 B loses
1011101-> 1+ 4*1 = 5 B loses
please correct me if my understanding is wrong but all the moves are forced , players intelligence will not have any impact on the game for equally beautiful, but if its "atleast" then this problem is very interesting indeed

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

I think there's still one thing to consider. For each round, as to the number of 0s -- N, we have two cases:  N = N-1, that's we move 0 in 1th bucket to 0th bucket. N = N, move 0 in ith bucket to (i-1)th bucket, here i>=2. And for each player, he'll try to keep N (remaining number of 0s after his round) to be even, so that he can always take the last round. I think this is what "play optimally" means in the question. So, we have

``````int finder(ArrayList<Integer> buckets, int player){
if (buckets.size()==1)
return getOpponent(player);
int N = getTotalNumberOfZeros(buckets, 1, buckets.size()-1);
if (buckets.size()==2)
return N%2==0 ? getOpponent(player): player;
if (N%2!=0){
moveZeroWithoutDecrement();
}else{
if (!1thBucketIsEmpty())
moveZeroWithDecrement();
else
moveZeroWithoutDecrement();
}
return finder(buckets, getOpponent(player));
}``````

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

As oldtimer said, the game ends when all ones are on the least significant bits.
So we basically need to count how many swaps we need to make the zeros go to the most significant bits.
For each bit set to 1, the number of swaps needed is equal to the number of 0s in the least significant bits.
If the total number of swaps is odd, player A wins, else B wins.

``````void Solve(int n) {
int i, zeros = 0, sum = 0;
for (i = 0; (i << 1) <= n; i++)
if ( n & (i << 1) ) // bit set to 1
sum += zeros;
else
zeros++;
if (sum & 1)
puts("Player A wins");
else
puts("Player B wins");
}``````

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

beaten by zero2 by a few secs :)

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

what if n= 11 written on board.....
the binary representation will be 
now second there can be no value of K for which you can get more then 4 one's for eq:
n-2^k

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

Why your thinking is restricted to 4 bit? and also the binary representation of 11 is 1011 and not 1111 which is for 15

n ranges from 0 to 10^9 (10 power 9) which is a 32 bit number and the number 4294967295 has 32 1's in it.

n-2^k = 4294967295

so the problem here is to find the number 'k' for a given 'n' written on the board in order to reach 4294967295

lets think and find out...

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

Forget about my comment, it doesn't make sense to think about the number which has 32 1's in it.

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

If the last move made by a player was such that allones in binary representation are moved to the lsb position then that player becomes the winner.

eg.
A : 10 
B : 9  -> diff.from previous = 2^0
A : 5  -> diff.from previous = 2^2
B : 3  -> diff.from previous = 2^1 ==> winner

eg.
A : 13 
B : 11  -> diff.from previous = 2^1
A : 7  -> diff.from previous = 2^2 ==> winner

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

if you have the value n, and the indexes for n = n[i]*2^i-1 + n[i-1]*2^i-2 + ... + n*2 + n
if you add the indexes a of the values n for which n[a] == 0, and that value is even, then team Friend 1 wins
if you add the indexes and that value is odd then Friend 2 wins

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

Brute force :

``````static bool IsWinner(int n)
{
bool result = false;

for (int i = 0; i < 31 && n > 1 << i; i++)
{
if ((n & (1 << i)) == 0 && (n & (1 << (i + 1))) != 0) // detect this one "10"
result |= !IsWinner(n - (1 << i));
}

return result;
}``````

The best solution :

``````static bool IsWinner2(int n)
{
int sum = 0;
int zeros = 0;
while (n > 0)
{
if ((n & 1) != 0) sum += zeros;
else zeros++;

n >>= 1;
}

return (sum & 1) != 0 ? true : false; // true - first player win, false - second player win
}``````

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

``````void judgeWinner(int n){
String b = Integer.toBinaryString(n);
int extra = 0;
for(int i = 1; i<b.length(); i++){
if(b.charAt(i) == '1')
extra ++;
}
int residual = (b.length()-1+ extra)%2;
if(residual == 0)
System.out.println("Player 2 wins");
else
System.out.println("Player 1 wins");
}``````

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

Based on the previous discussion, we can change the question to judge the number of moves to compact the number so at last all the number 1 get stay together, like '11111'. So in order to calculate the total number of moves, we can go through the following ways. First, find the first occurrence of 0 in the sequence. Then find the number 1 just behind this first 0. Then the moves for this round should be the subtract of both first 0 and 1 after it. Then we swap these two numbers in the array.
We keep on the process until we cannot find number 1 after the so called first 0. Then the total number of moves will be the judge base. Let it as count. If count is odd, then that means player 1 wins. Otherwise player 2 wins. The code are attached below, I just print the total move number:

``````public class WinnerCount {
public static int firstZeroPosition(int[] array) {
for(int i = 0; i < array.length; i++) {
if(array[i] == 0)
return i;
}

return -1;
}

public static int firstOneAfterZero(int[] array) {
int firstZero = firstZeroPosition(array);
if(firstZero >= 0) {
for(int i = firstZero + 1; i < array.length; i++)
if(array[i] > 0)
return i;
}

return -1;
}

public static int count(int[] array) {
int count = 0;
int firstIndex = firstOneAfterZero(array);
while(firstIndex > 0) {
int firstZero = firstZeroPosition(array);
count += firstIndex - firstZero;
swap(array, firstZero, firstIndex);
firstIndex = firstOneAfterZero(array);
}

return count;
}

public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

public static void main(String[] args) {
int[] a = {0, 1, 0, 1, 0, 1};
System.out.println(count(a));
}
}``````

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

f(1) = false;
f(n) = !f(n-2^0) | !!f(n-2^1) ... !f(n-2^k) (2^k < n)

``````bool win(int n){
if (n == 1)
return false;
for(int i=0; i<n; i++)
{
int m = pow(2, i);
if (m >=n){
break;
}
// if (!samebeauty(n, m)) continue;
if (!win(n-m)){
return true;
}
}
return false;
}``````

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

is this for phone interview or on site?

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

Isn't the question to come up with a number that has same number of 1's as the given number before they all run out? If yes, it would be n!/a!(n-a)! where n is the number of all binary digits the max number (10^9) can have, and a is the number of 1's in the given number x. If the result is even one wins otherwise...

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

assume binary representation of n is of the form

ak ones b(k-1) zeros .... a3 ones b2 zeros a2 ones b1 zeros a1 ones

where ai>0 and bj > 0 (if no zeros at all P2 win)

#swaps to more all ones to least significant positions while staying beautiful would be
s = a2*b1 + a3*(b1+b2) + ... ak*(b1+b2+...b(k-1))

if(s is even) P2 win
else P1 win

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

If ((total number of bits in n (whether zero or one) - # of one bits in n) & 1) A wins else B wins

If the number of 1s in n is odd, A wins else B wins.

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.