technology and zen of life

“A heisenbug (named after the Heisenberg Uncertainty Principle) is a computer bug that disappears or alters its characteristics when an attempt is made to study it.”

Algortihm Challenge 1: No division!

I have decided to come up with series of challenges n problems which are algorithmic in nature and are asked in interviews of reputed companies like Microsoft, Google.

This one was asked in a Google interview recently. Try to answer it in your comments. I will post the solutions if no one comes up with the right answer (let’s hope not).

“You have an unordered array X of N integers. Find the array M containing N elements where M_i is the product of all integers in X except for X_i. You may not use division. You can use extra memory.

What is the best way of doing this?”

Example:

N=4

X = {2, 5, 3, 7}

M_0 = 5*3*7 = 105

M_1 = 2*3*7 = 42

M_2 = 2*5*7 = 70

M_3 = 2*5*3 = 30

M = {105, 42, 70, 30}

(hint: There are solutions faster than O(N^2))

NOTE: while posting solution put your code (if any) inside <code></code> tags.


SOLUTION:
Thanks for your efforts. The solution presented here runs in O(N) time. Yes O(N), and thats what an interviewer would expect you to come up with, in less than an hour.

Form two arrays P and Q such that
P[1] = 1
P[i] = X[1] * X[2] * … * X[i-1] for 1 < i <= N
 
and
 
Q[i]  = X[i+1]*X[i+2]*… * X[N] for 1 <= i < N
Q[N] = 1
 
Set M[i] = P[i]*Q[i]
 
Both P and Q (i.e. M) can be found in O(N) time.

Once can access corresponding code snippet here.

Leave a Reply

19 Responses

  1. pavan says:

    The solution is the first of the questions in the page

    http://placementsindia.blogspot.com/2007/12/solutions-to-few-google-top-interview.html

    Easier than what I anticipated.. lot at me 😀

  2. Andrew says:

    Why can’t you just do this?:


    function algorithm_challenge(int &X, int N, int &M)
    {
    // Initialize local variables.
    int i = 0;
    int product = 0;

    // Compute base product.
    for (i = 0; i < N; i++)
    {
    product += X[i];
    }

    // Now compute M[i].
    for (i = 0; i < N; i++)
    {
    if (X[i] == 0)
    {
    M[i] = 0;
    }
    else
    {
    M[i] = product / X[i];
    }
    }
    }

  3. Sharath says:

    Here is my Soln…


    m[0] = 1;
    // Put cumulative products into M array...
    for(i from 2 to n){
    m[i] = m[i-1]*x[i];
    }

    // Start from back and compute the reverse cumulative products in a temp variable, and store the final product back into M array..

    temp = 1;
    for(i from n to 1){
    m[i] = m[i] * temp;
    temp = temp*x[i];
    }

    Like in the soln given, n + 2n = 3n multiplications.. but only one extra temp variable.. instead of two extra long arrays…

  4. Sharath says:

    Lets try better.. I have a similar algo that reduces the space complexity to O(1).. here the space complexity is O(n).. to be exact, O(2n). Actually it is not that very different.. just a little tweaking to the soln here and there…

  5. jodhpuriguy says:

    good algo (and the problem itself too)!

  6. Gaurav says:

    cool.
    ok bond!
    my mistake. :)
    nice one!

  7. Fr0z3n says:

    I have added a code snippet here http://snippets.dzone.com/posts/show/4226

    As you can see through the code snippet, my approach does a total of 3N multiplications, while others are doing N^2 mutiplications. Hence my approach is O(3N) or O(N).

    Hope you get a better picture now.

  8. Gaurav says:

    hey frozen, i am really out of touch with algo and coding for some days,can you answer some questions for me:

    1. What is the difference between Complexity (big O) and number of computations?

    2. I understand that the solution you gave is O(N), but what I fail to understand is that the number of computations (assuming one multiplication to be one computation), is still same as Dark’s solution. Then how can it be claimed that this solution is better than Dark’s?
    (Correct me if I am wrong and the questions that I ask may sound naive, but i really want to know, I dont understand language of wikipedia and all)

  9. Fr0z3n says:

    Stay tuned! Another Algorithm Challenge is on its way 😉

  10. Fr0z3n says:

    Well. I guess this wordpress blog is not friendly for us to ask for solutions in comments. Next time onwards I will think of some other method of accepting solutions.
    Thanks for your efforts. Ben and Dark have suggested the approach which anyone would come up with on the first time but runtime being O(N^2)
    I am not able to understand what Gaurav is suggesting, but i assume he is suggesting a different solution than what i had in my mind and which runs in O(N) time. Yes O(N), and thats what an interviewer would expect you to come up with, in less than an hour.
    The solution has been added to the actual post.

  11. Gaurav says:

    Finally I know how to post it right!!


    //Initializing
    for (int i=0; i<N; i++)
    {
    temp[0][i] = X[i]; //Leaves of the tree
    M[i] = 1;
    }

    //Forming the tree with pair wise multiplication
    int j =1;
    for (int t=1; t &lt =logN; t++)
    {
    j *= 2;
    for ( int k=0; k &lt N/j; k++)
    {
    temp[t][k] = temp[t-1][2*k] * temp[t-1][2*(k+1)]
    }
    }

    //Multiplying one number from each level of tree for each element in the array M
    j = 0.5;
    for (int t=logN; t &gt =0; t++)
    {
    j *=2;
    for (int i=0; i &lt N; i++)
    {
    for (k=0; k &lt t; k++)
    {
    if ( i &lt ( k*j) &amp&amp i &gt (k-2)*j)
    {
    M[i] *= temp[t][k]
    }
    }
    }
    }

    I really need to learn HTML and revisit my datastructures :(

    And I dont even know if this code is right

  12. Gaurav says:

    This is the code for above explanation


    //Initializing
    for (int i=0; i<N; i++)
    {
    temp[0][i] = X[i]; //Leaves of the tree
    M[i] = 1;
    }

    //Forming the tree with pair wise multiplication
    int j =1;
    for (int t=1; t
    I hope the idea is correct, I dont really know about the code.
    form a tree structure by multiplying.

    I am sorry about shitting so much all over :(

  13. Gaurav says:

    I dont know what is wrong.
    Delete the crap comments. will post again, sometime

  14. DarK says:

    Gaurav you need to change the less than symbols to their html codes..

    the html code is
    & l t ;

    type it without spaces

    it gives <

  15. Gaurav says:

    wtf!!!

    where did my comment go!
    I worked an hour to write the code.

  16. DarK says:

    i hope this one works.. it will be O(N^2) working on faster solution

    for (int i = 0; i < N; i++)
    {
    M[i]=1;
    for(int j = 0; j < N; j++)
    {
    if (i==j) continue;
    M[i] *= N[j];
    }
    }

  17. Ben says:

    Well, this is my last try. I’m going to change the less-than signs. You can delete my other posts. I feel bad

    for (int i = 0; i < N; i++)
    {
    M[i] = X[(i + 1) % N];
    for (int j = 0; j < i; j++)
    M[i] *= X[j];
    for (int j = i + 2; j < N; j++)
    M[i] *= X[j];
    }

  18. Fr0z3n says:

    Please complete your solution. You can put your code inside <code></code> tags.

  19. Ben says:

    This one definitely is a tough one for me. I love programming puzzles! Of course I don’t claim to be a algorithm god in any way, I just think they’re fun, but I couldn’t wrap my mind around how to do this faster than O(n^2). I can’t wait to see the answer! All I could think of was probably the most obvious, but I’ll share it anyway:

    for (int i = 0; i

Email Subscription

Disclaimer

The views expressed on this blog are personal. We do not claim to be a representative voice of the views of any organisation whatsoever. We are not responsible for the content present on the blogs to which we have linked.Views expressed are solely that of the author and does not reflect a collective opinion of contributors.
%d bloggers like this: