Global Scholar Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


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

step-1 create a max heap out of the array
step-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

- raja roy on January 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

we can also use sorted array... same

- Sanjay Kumar on January 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can keep only 3 nodes in the max heap, and only two nodes in min heap, thus reaching the O(n) complexity.

- tsichevski on January 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should it be:

if((mina *minb) > (maxa*maxb))
    then MaxProduct = mina *minb * maxa  ??

- Anonymous on January 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should it be?:

if((mina *minb) > (maxa*maxb))
    then MaxProduct = mina *minb * maxa  ??

- Anonymous on January 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It should be
if(maxb*maxc<mina*minb)
mina*minb*maxa

- Shankar on January 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it shoulbe MAX (
min-1 * min-2 * min-3,
min-1 * min-2 * max-1 ,
max-1 * max-2 * max-3
)

If building two heaps is considered inefficient in terms of space/time, we can just scan array once to keep track of 3-Max & 3-Min values..

- saga on January 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pramodhn91 on January 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about -6 -5 1 2 5 6 ..?? max is 180 but your output is 60

- Sanjay Kumar on January 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It does give 180. That is the reason 2 min values have been chosen in prod1!!

- pramodhn91 on January 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is it not possible to traverse through the array once to find the largest 3 numbers (abs value) and multiply those 3?

- A on January 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kalai on May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

time complexity is 2+(n-3),so o(n-1)

- kalai on May 03, 2012 | Flag


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More