## Google Interview Question for Software Engineer / Developers

• 2

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

ith bit of missing element would be :

zor of ith bit of all element in list and ith bit of 1 to n. So all duplicates will be nullified and missing elements bit will remain. Here is the quick code(may be buggy :))

``````for(i=0;i<32;i++)
{
ithBit = 0;

//xor with array elements
for(int k=0; k<n; k++)
{
ithBit ^= A[(k+1)*32-1];
}

//Xor with 1 to n
for(int k=1; k<=n; k++)
{
ithBit = (k & (1<<i))>>i;
}

result[i] = ithBit;
}``````

result[i] will be a 32 bit array having missing element. Hope it helps.

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

Code is correct only if n = pow ( 2, i) - 1
if n == 4 for example
list will be,
001
010
011
100

Xoring will not work in the case, the last bit occurances is 1

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

Well you have not considered that one element is missing. It should work in that case too.

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

I din get the question yet.

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

@binu
How can we identify the value of A[i] with just log(A[i]) operations ?For example if the input is 7 ie. 111 I need 3 read operations to identify that I have read 7. but 3 is greater than log7

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

You can read only one bit in one read operation. What I meant was, number of read operations required to read a number n, is a linear function of log(n).
If log(n) is integer, then number of operations = log(n)+1.
If log(n) is not an integer, then number of operations = ceil(log(n)), where ceil(x) = smallest integer greater than x. log(n) is of course base 2 logarithm of n.
Sorry for not explaining it earlier.

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

Why it is log(A[i]) to read an integer.
Because we do not know what A[i] is, we need to read all bits until integer bits size like 32

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

we can find the missing number by counting the number of bits set at each bit position for all the n-1 numbers. i.e add up numbers of bits set at bit 0 of all numbers. and Do the same for bit1, bit2 etc.
If n is a power of 2 , it will be easier to arrive at a solution. If not then we need bit more logic to calculate it. Run through with sample input to know what i mean.

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

Yes if the number is power of 2 then this works. If its not then it may not work. But one way we can add extra numbers to make it power of 2.

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

Let C = Xor of all the elements from 1 to n. O(n) time. Let C' = Xor of the elements read in....let each element have t bits (on average) . So, time taken = n*t*n. Let A = missing no. C = A XOR C'. So, A = C XOR C'.

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

This procedure works for the case in which there is only one number missing. What if there are more than two numbers missing?

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

There is only one missing number!!

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

There is only one missing number!!

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

There is only one missing number!!

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

There is only one missing number!!

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

There is only one missing number!!

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

There is only one missing number!!

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

For solving the above algorithm we will need to use the concept of xor we will xor all the array elements and also xor all the numbers from 1 to n and finally xor both the xor of arrays and numbers together.

Implementation:

``````int findmissing(int arr[], int n){
int xor_number = 1;
int xor_array = arr[0];
for(int i = 2; i <= n + 1; i++)
xor_number = xor_number ^ i;
for(int i = 1; i < n; i++)
xor_array = xor_array ^ arr[i];
return xor_array ^ xor_number;``````

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

read a[i] in log(a[i])...this is insane

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

don't get the question

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

This is in the CareerCup Cracking the Coding interview and the solution is fairly clever.

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

what's the solution?

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

add 'em up and subtract it from n(n+1)/2

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

this is the problem discussed in programming pearl, apply binary search based on bit set.

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.