## Facebook Interview Question for Software Engineer Interns

• 0

Country: United States
Interview Type: Phone Interview

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

c++, implementation

``````typedef unsigned long long UINT64;

UINT64 getXOROne2N(UINT64 n) {
switch (n % 4) {
case 0: return n;
case 1: return 1;
case 2: return n + 1;
case 3: return 0;
}
return 0;
}``````

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

Nice solution, Can you please explain the logic ?

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

@Paul:
It's easy to see the cyclicity:
As a start:
1 mod 4 = 1.
1 xor 0 = 1.
Then in the 2nd step (n mod 4 = 2) you xor an even number (ie ending 0 in binary) with 1, thus it will always result in n+1.
In the third step (n mod 4 = 3) you xor a number by itself (the result was n+1 in the previous iteration), which naturally returns 0.
In the last step (n mod 4 = 0) you xor a number by 0, which results in the number itself.
Since that's even you will xor that with n+1, which is odd, the only bit difference will be the least significant, thus will result in 1 and the cycle starts over.

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

``````#define FOLD(X)\
X |= X >> 1;\
X |= X >> 2;\
X |= X >> 4;\
X |= X >> 8; \
X |= X >> 16; \
X |= X >> 32

unsigned long long XOR(unsigned long long N)
{
unsigned long long Res = 0;
unsigned long long Original = N;

if (N == 1)
{
return (1);
}

while (N > 1)
{
unsigned long long Closest = N;
FOLD(Closest);
Closest ^= Closest >> 1;
Res |= (Original - Closest + 1) % 2 ? Closest : 0;
N = N & (Closest - 1);

if (N == 0)
{
Res += (Original % 2) ? 0 : 1;
break;
}
}

return (Res);
}``````

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

#include <stdio.h>

int main()
{
int n;
long long value;
printf("Enter number : ");
scanf("%d", &n);
value = n--;
while (n > 0) {
value = value ^ n--;
}
printf("Value = %lld\n", value);
}

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

value = n--;
while (n > 0) {
value = value ^ n--;
}

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

``````unsigned int CalcXorFrom1ToN(int n)
{
if (n % 2 == 0)
return n;
else
return n ^ (n-1);
}``````

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

``````if n%4==0:
print n
elif n%4==1:
print 1
elif n%4==2:
print (n/4)*4+3
else:
print 0``````

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

``````value = n--;
while (n > 0) {
value = value ^ n--;
}``````

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

In Ruby (2.0 or above):

``````def f(n)
(1..n).inject {|a,b| a^b }
end``````

or shorter version:

``````def f(n)
(1..n).inject(:^)
end``````

Comment hidden because of low score. Click to expand.

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.