Google Interview Question for Software Developers
- 2of 2 votes
AnswerWas asked at GHCI Bangalore at their booth for a prize and perhaps hiring interns or experienced software developers.
- jaryya@hawk.iit.edu November 10, 2019 in India
Find the return value for N=100
int returnAns(int N){
int ans=0;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
ans +=((i & -i) == (j & -j)?1:0); //the question missed the condition and was returning a boolean, so I added it myself
}
}
return ans;
}
My answer: 0 ; their answer: 1610, hence got it wrong.
My explanation: I assumed negative of i in binary to be
simply represented by setting the MSB to 1 e.g. for 8 bit representation of 3: +3 is 0000 0011 and -3 is 1000 0011. In the inner loop the value of ans will always evaluate to 0 since Bitwise & of these i and -i or j and -j will always result into i and j respectively. (undergrad computer organization concept.)
Negative numbers can also be represented as 1s and 2's complement and in all modern machines by architecture its 2s complement.
Now if we assume 1's complement, +3: 0000 0011 and -3: 1111 1100. so bitwise & of these two is 0 and so the value of ans will always be incremented by 1. By two loops 100+99+98+97+...+1 = 100*101/2 (i.e. n*(n+1)/2)
Then 2's complement, which is the most relevant representation of signed binary numbers.
Odd numbers:
+3: 0000 0011 -3: 1111 1101 Binary & is 0000 0001.
For all even numbers:
+4: 0000 0100 and -4: 1111 1011+0000 0001 = 1111 1100 and Bitwise & of 4 and -4 is 0000 0100 which is 4.
So, in the innermost loop ans is incremented by 1 when i is odd and j is also odd. ie. when i is 1, 3, 5, 7... 97 and j is 3, 5, 7, 9,...,99 ans is added 1(return value of true ==) when calculated it comes to 1610.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm
Say , SUM(n) = n*(n-1)/2
- monimisimao June 13, 2020Observations :
----------------------
(1) -i == (2's complement of i) + 1
(2) (i & -i) == 1 if i is odd
(3) (i & -i) == 2^x if i is even ; x = number of trailing 0s in binary representation of i
Odd case :
-----------------
*** How many (i,j) (i<j) pairs will give (i & -i) == (j & -j) == 1 ??
Ans : SUM(50) = 1225 ;
--------
How?
----------
There are 50 odd numbers in range [0,100).
for (i == 1) => 49 odd pairs
for (i == 3) => 48 odd pairs
for (i == 5) => 47 odd pairs
and so on...
so, 49 + 48 + 47 + ....... + 1 = SUM(50) = 1225 ;
Even Case:
------------------
How many pairs (i,j) (i<j) with same number of trailing zeroes in their binary rep. ?
Ans :
--------
How many numbers in range [0,100)
=> with 1 trailing 0 == 99/2 - 99/4 = 49-24 = 25;
=> with 2 trailing 0s == 99/4 - 99/8 = 24-12 = 12;
=> with 3 trailing 0s == 99/8 - 99/16 = 12-6 = 6;
=> with 4 trailing 0s == 99/16 - 99/32 = 6-3 = 3;
=> with 5 trailing 0 == 99/32 - 99/64 = 3-1 = 2;
So, Number of pairs with same number of trailing 0's :
SUM(25) + SUM(12) + SUM(6) + SUM(3) + SUM(2) = 385
So, Total : 1225 + 385 = 1610
----------------------------------------------------------X----------------------------------------------
Thanks for posting this nice problem (^_^)