COME ON CODE ON

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
Example:
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

Advertisements

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
    //solution
    res=0;
    for(i=0;i<n;i++){
    res=res XOR i
    if(i<n-1)
    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

    Neeraj

    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];
      }
    }

    nthrgeek

    November 29, 2009 at 9:49 PM

    • nice solution and yes you are right.

      fR0D

      November 29, 2009 at 9:59 PM


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: