Google Interview Question: Given an array of numbers, re... | Glassdoor

Interview Question

Senior Software Engineer Interview Mountain View, CA

Given an array of numbers, replace each number with the

  product of all the numbers in the array except the number itself *without* using division.
Answer

Interview Answer

8 Answers

14

O(size of array) time & space:
First, realize that saying the element should be the product of all other numbers is like saying it is the product of all the numbers to the left, times the product of all the numbers to the right. This is the main idea.
Call the original array A, with n elements. Index it with C notation, i.e. from A[0] to A[n - 1].
Create a new array B, also with n elements (can be uninitialized). Then, do this:
Accumulator = 1
For i = 0 to n - 2:
  Accumulator *= A[i]
  B[i + 1] = Accumulator
Accumulator = 1
For i = n - 1 down to 1:
  Accumulator *= A[i]
  B[i - 1] *= Accumulator
Replace A with B
It traverses A twice and executes 2n multiplicates, hence O(n) time
It creates an array B with the same size as A, hence O(n) temporary space

Jordan on Sep 11, 2010
2

# A Python solution (requires Python 2.5 or higher):

def mult(arr, num):
    return reduce(lambda x,y: x*y if y!=num else x, arr)

arr = [mult(arr,i) for i in arr]

# O(n^2) time, O(n) space

rotoiti on Sep 25, 2010
10

Create two more arrays. One array contains the products of the elements going upward. That is, B[0] = A[0], B[1] = A[0] * A[1], B[2] = B[1] * A[2], and so on. The other array contains the products of the elements going down. That is, C[n] = A[n], C[n-1] = A[n] * A[n-1], and so on.

Now A[i] is simply B[i-1] * C[i+1].

pflau on Oct 6, 2010
2

def without(numbers):
    lognums = [math.log10(n) for n in numbers]
    sumlogs = sum(lognums)
    return [math.pow(10, sumlogs-l) for l in lognums]

xamdam on Oct 7, 2010
7

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 on Jun 10, 2011
0

#include

#define NUM 10
int main()
{
        int i, j = 0;
        long int val = 1;

        long A[NUM] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        // Store results in this so results do not interfere with multiplications
        long prod[NUM];

        while(j < NUM)
        {
                for(i = 0; i < NUM; i++)
                {
                        if(j != i)
                        {
                                val *= A[i];
                        }
                }
                prod[j] = val;
                i = 0;
                val = 1;
                j++;
        }

        for(i = 0; i < NUM; i++)
                printf("prod[%d]=%d\n", i, prod[i]);

        return 0;
}

Rohan on Jun 20, 2011
1

void fill_array ( int* array, size ) {
int i;
int t1,t2;

t1 = array[0];
array[0] = prod(1, size, array );

for(i = 1; i < size; i++){
  t2 = array[i];
  array[i] = prod(i, array.size(), array)*t1;
  t1 *= t2;
}

int prod(start, end, array){
  int i;
  int val(1);

  for(i = start; i < end; i++ )
      val *= array[i];

  return val;
}

Devin on Aug 25, 2011

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.