Global Scholar Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
You can keep only 3 nodes in the max heap, and only two nodes in min heap, thus reaching the O(n) complexity.
int prod3(int arr[], int size)
{
int i,max1,max2,max3,min1,min2;
max1=max2=max3=min1=min2=arr[0];
for(i=0;i<size;i++)
{
if(arr[i]>max1)
{
max3=max2;
max2=max1;
max1=arr[i]; //Max Value
}
else if(arr[i]>max2)
{
max3=max2;
max2=arr[i] //2nd Max value
}
else if(arr[i]>max3)
{
max3=arr[i]; //3rd max value
}
if(min1<arr[i])
{
min2=min1;
min1=arr[i]; //Min value
}
else if(min2<arr[i])
{
min2=arr[i]; //2nd Min value
}
}
int prod1,prod2;
prod1=min1*min2*max1;
prod2=max1*max2*max3;
if(prod1<prod2)
return prod2;
else
return prod1;
}
take three variables a,b,c
for(i=0;i<=1;i++)
{
a=a+b;b=a-b;a=a-b;
b=b+c;c=b-c;b=b-c;
}
for(i=3;i<n;i++)
{
if(a[i]>a)
{
t=a;t1=b;
a=a[i];b=t;c=t1;
}
else if(a[i]>b)
{
b=c;c=a[i];
}
else
{
if(a[i]>c)
{
c=a[i];
}
}
}
step-1 create a max heap out of the array
- raja roy January 22, 2012step-2 create a min heap out of the array(only if the array contains -ve nos)
step-3 delete three elements(say maxa, maxb, maxc) from the max heap these elements would the 3 largest elements in the array
step-4 if the array contains -ve elements then delete TWO elements(say mina, minb) from the min heap.
step-5 If the array contains -ve elements then check
if((mina *minb) > (maxa*maxb))
then MaxProduct = mina *minb * maxc
else
MaxProduct = maxa*maxb*maxc
Total time would be = O(nlogn) which could be reduce to O(n) if you create using fast heap