## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
12
of 12 vote

left_partial = 1;
right_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

Comment hidden because of low score. Click to expand.
0

Gud One

Comment hidden because of low score. Click to expand.
0

Amazing Solution!

Comment hidden because of low score. Click to expand.
0

awesome...

Comment hidden because of low score. Click to expand.
0

Gud solution.

Comment hidden because of low score. Click to expand.
0

How is this algo O(n). 2 for loops going from 0-n makes it O(n2)

Comment hidden because of low score. Click to expand.
0

@newguy...it will make 2n not n2.......one loop is not inside another....!

Comment hidden because of low score. Click to expand.
0

this sol rocks.... thanks

Comment hidden because of low score. Click to expand.
0

Awesome Solution !

Comment hidden because of low score. Click to expand.
0

nice one...

Comment hidden because of low score. Click to expand.
0

Well thought ... :)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

awesome solution!!

Comment hidden because of low score. Click to expand.
0

very good solution......

Comment hidden because of low score. Click to expand.
6
of 6 vote

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]

Comment hidden because of low score. Click to expand.
0

awesome.. works just fine!

Comment hidden because of low score. Click to expand.
0

Nice answer but though the space complexity is O(n)

Comment hidden because of low score. Click to expand.
0

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;
}

Comment hidden because of low score. Click to expand.
0

gud one

Comment hidden because of low score. Click to expand.
0

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;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

Comment hidden because of low score. Click to expand.
0

Srimanyu.. nice one! i thought the same! simple but do you think one can reduce the time complexity from O(sq(n)) to O(n)?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

workable idea... good one!

Comment hidden because of low score. Click to expand.
0

sir please show me any method for performing division by bitwise operators

Comment hidden because of low score. Click to expand.
0
of 0 vote

int prod =1;
for(int i=0;i<n;i++)
prod = prod*arr[i];

for(int i=0;i<n;i++)
prod[i] = prod/a[i];

is this solution acceptable?

Comment hidden because of low score. Click to expand.
0
of 0 vote

no its not. problem says you should not use / operator

Comment hidden because of low score. Click to expand.
0
of 0 vote

no its not. problem says you should not use / operator

Comment hidden because of low score. Click to expand.
0
of 0 vote

What if the integer array contains a zreo? You cannot use divide in this case.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.