Interview Question for Senior Software Engineer at Google:

Create a tree, where the leaf nodes are the initial values in the array.

Given array A[1..n]
create array B[1..n]= {1} // all elements =1 ;
for (i=1; i<=n; i++) {
 for (j=1; j<=n; j++ ) {
 if (i<>j) B[i] *=A[j];
  }
}
A=B;

To husb:

Your answer will work, but it's O(n^2) solution. Can you do better?

Am I missing something? It can't be this easy:

given array[0..n]

int total = 0;
for(int i=0; i<=n; i++)
{ total += array[i]; }

for(int i=0; i<=n; i++)
{
array[i] = total-array[i];
}

Ah yes.. I was. The question is PRODUCT, not sum. That will teach me to read the question too fast ;)

Create a tree, where the leaf nodes are the initial values in the array. Build the binary tree upwards with parent nodes the value of the PRODUCT of its child nodes. After the tree is built, each leaf node's value is replaced by the product of all the value of the "OTHER" child node on its path to root. The pseudo code is like this

given int array[1...n]

int level_size = n/2;
while(level_size != 1){//build the tree
      int new_array[1...level_size];
      for ( int i=0; i<level_size; i++){
           new_array[i] -> left = array[i*2]; (and also from child to parent)
           new_array[i] -> right = array[i*2+1]
          new_array[i] = new_array[i] -> right* new_array[i] -> left; (take the product)
      }
      array= new_array;
      level_size /=2;
}

for(int i=0; i<n;i++){//replace
    array[i] = replace(array[i]);
}

int replace(node n){
    int p = 1;
   node parent, brother;
   while(node != root){
        parent = node->parent;
       if( parent->left == node){//find the other node under the parent
          brother = parent->right;
       }
      else{
           brother = parent->left;
       }
        p *= brother;
       node = parent;
    }
    return p;
}

btw, it's O(n*logn)

It seems to me that for any number array[i], you're looking for

PRODUCT(all array[j] where j < i]) * PRODUCT(all array[j] where j > i])

we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So,

leftProduct[0] = array[0];
for j=1; j < n; j++
  leftProduct[j] = leftProduct[j-1]*array[j];

rightProduct[n-1] = array[n];
for j=n-2; j >= 0; j--
  rightProduct[j] = rightProduct[j+1]*array[j];

then to get our answer we just overwrite the original array with the desired product

array[0] = rightProduct[1];
array[n-1] = leftProduct[n-2];
for j=1; j < n-1; j++
  array[j] = leftProduct[j-1] * rightProduct[j+1]

and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell.

betterStill, I think you have the answer the interviewer wanted..

But... if the array is google sized, don't we have to worry about overflows?

it looks to me can be done in order n time given the following relation:
product[n] = product[n-1]*array[n-1]/array[n]
for example we have array 2 3 4 5 6
product[0]=3*4*5*6
product[1]=2*4*5*6
array[0] = 2;
array[1]=3
product[1]=product[0]*array[0]/array[1]

Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e.
tolal = A[0]*A[1]]*....*A[n-1]
now take a loop of array and update element i with A[i] = toal/A[i]
Since division is not allowed we have to simulate it.
If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g.
2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input

void ArrayMult(int *A, int size)
{
    int total= 1;
    for(int i=0; i< size; ++i)
        total *= A[i];
    for(int i=0; i< size; ++i)
    {
        int temp = total;
        int cnt = 0;
        while(temp)
        {
            temp -=A[i];
            cnt++;
        }
        A[i] = cnt;
    }
}
Speed in O(n) and space is O(1)

narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000
so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else....