Microsoft Interview Question
Software Engineer / Developersthen it's even more simpler. in list B, except for the entry at which the zero is present, all other entries will be zero. for the entry at which zero is present, just multiply the other entries. if there are more than one zeros in list A, then all entries in list B are zeros.
We can calculate the array B in the following manner.
1. First iterate thru Array A (from i=1 to n) and for each value of A[i] store the product of A[1] ..A[i-1] elements in B[i].
2. Next iterate thru array A (from i=n to 1) and for each value of A[i] store the product of A[i-1] .. A[n] in B[i].
3. After the steps 1 and 2 we will have the required values in array B
code for the same is as follows:
void foo(const int A[], const int len)
{
int B[len];
int prod = 1;
int i=0;
for(i=0;i<len;i++)
{
B[i] = prod;
prod *= A[i];
}
prod = 1;
for(i=len-1;i>=0;i--)
{
B[i] = prod;
prod *= A[i];
}
for(i=0;i<len;i++)
{
printf("%d\t", B[i]);
}
}
long * product (int *a, int n)
{
int i, count =0;
long product = 1;
//if empty string..
if(n==0)
return NULL;
//Allocate the memory which is initialized to zero...
int *p = calloc(n, sizeof(int));
//Find the product
for(i=0; i<n; i++)
if(a[i] == 0)
count++; //Count number of zeros
else
product = a[i]*product;
if(count > 1) //Everything is zero.. juz return the p
return p;
for(i=0; i<n; i++)
if ( a[i] == 0)
p[i]=product;
else
p[i]=product/a[i];
return p;
}
Nobody though about the overflow???
So to avoid this condition, one must check if the multiplication would lead to the overflow condition. If it does, one should simply divide the product by the number we have while iterating and hence in the worst case it may lead to O(n2) complexity.
One should also ask that even after division, if there is overflow what should be done.
Working code!!
main()
{
int i,l,r,x[5]={5,3,4,1,2},y[5]; // x is the initial array, y is the final array
int n = 5; // n be the size of the array, here already defined as 5
l = 1; // l is the product of the values of the left side of an index in x
r = 1; // r is the product of the values of the right side of an index in x
for (i=0 ; i<5 ; i++) y[i]=1; // initialising all y values to 1
for (i=0 ; i<5 ; i++)
{
y[i] = y[i]*l ;
y[n-i-1] = y[n-i-1]*r;
l = l*x[i];
r = r*x[n-i-1];
}
for (i=0; i<5; i++) printf("%d\n",y[i]);
getch();
}
Multiply all the elements and create a master product value. Then traverse the array and just divide the master product with the element in the corresponding spot and store it. This is linear time.
- Vivek March 01, 2008