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.

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.