Global Scholar Interview Question for 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 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 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 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 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 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 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 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 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 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 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 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 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 May 03, 2012 | Flag


Add a Comment
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.

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