A blog about programming and more programming.

Google Interview Questions

with 3 comments

All the below questions are to be done in O(n) time complexity.

1>Given an array of size n-1 whose entries are integers in the range [1, n], find an integer that is missing. Use only O(1) space and treat the input as read-only.

2>Given an array of size n-2 whose entries are integers in the range [1, n], find two integer that are missing.

3>There is an array A[N] of N integers. You have to compose an array B[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i].

or Formula
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Solution :

1>Let the missing number be M. We know that the sum of first N natural numbers is N*(N+1)/2. Traverse through the array once and calculate the sum. This is the sum of First N natural numbers – M or S=N*(N+1)/2 – M. Therefore M = N*(N+1)/2 – S.

2>Similar approach to the first one. Traverse the array once and calculate its sum and multiplication. Let the sum be S and multiplication be M. Let the missing numbers be P and Q. From above we know that P+Q = N*(N+1)/2 – S. Also P*Q = N!/M. So we can get P and Q from these two equations.

3> Lets first see the C++ solution.
void solution(vector A)
    int N=A.size(),i,j;
    vector L(N,0);
    vector R(N,0);
    vector B(N,0);
    for (i=0,j=N-1; i=0 ;i++, j–)
        L[i] = i==0? 1 : A[i-1] * L[i-1];  
        R[j] = j==N-1? 1 : R[j+1] * A[j+1];  
    for (i=0; i


Written by fR0DDY

March 5, 2009 at 3:35 PM

Posted in Programming

Tagged with , , , , ,

3 Responses

Subscribe to comments with RSS.

  1. There may be better solutions for Qno. 1 and 2
    for qno. 1
    res=res XOR i
    res=res XOR arr[i]
    after end of this loop res is the missing number

    for qno.2
    //repeat the above process
    res is then XOR of two missing numbers
    Now the question is can you find two numbers if there xor is given and you know the range in which they lie??
    if you can find then do let me know..
    The xor method is most generic and works even the sum of nos. exceeds the storage limits. this would be more of concern in 2nd case where we have n!
    This method uses the property that x (*) x=0 and XOR is associative


    March 6, 2009 at 2:13 PM

  2. For the third problem : my solution consists of only one loop + you have used lots of extra spaces which is not at all necessary.

    Some home cooked codes in C:

    void ArrayMul(int buf[],int res[],size_t len) /*res[] is assumed to be of size len & all members initialized to 1 */
      size_t i;
      int left = 1,
    		right = 1;
      for(i = 0; i<len;i++)
    	  res[i] *= left;
    	  res[lenn-i-1] *= right;
    	  left *= buf[i];
    	  right *= buf[len-i-1];


    November 29, 2009 at 9:49 PM

    • nice solution and yes you are right.


      November 29, 2009 at 9:59 PM

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: