## Microsoft Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Written Test

Could someone please tell what could be the input and expected output for easy understanding of this question?

if element stored in int e[];

go from begin to tail, h[i]=h[i-1]*e[i]

go from tail to head, t[i]=t[i+1]*e[i]

then the result is prod[i]=h[i-1]*t[i+1]

can be done in-place

for (int i = 0; i < l; i++) {

partial_prod_start *= arr[i];

partial_prod_end *= arr[l - 1 - i];

if (i + 1 < l) prod[i + 1] *= partial_prod_start;

if (l - 1 - i -1 >= 0) prod[l - 1 - i -1] *= partial_prod_end;

}

int main()

{

int i,j,pro=1;

int prod[5],arr[10]={1,2,3,4,5};

for(i=0;i<5;++i)

{

for(j=0;j<5;++j)

{

if(i==j)

continue;

else

pro=pro*arr[j];

}

prod[i]=pro;

pro=1;

}

for(i=0;i<5;++i)

printf("%d\t",prod[i]);

printf("\n");

return 0;

}

Multiply all the numbers in one variable and than traverse the array and divide the product by the i-th to store i-th product value using division without using the division operator.

Division can be done using bit shifting method.

left_partial = 1;

- Anonymous September 18, 2011right_partial = 1;

for (i = 0 ; i < n; i++)

{

prod[i] = left_partial;

left_partial *= arr[i];

}

for (i = n - 1; i >= 0; i--)

{

prod[i] *= right_partial;

right_partial *= arr[i];

}

O(n) time complexity

O(1) space complexity