Amazon Interview Question Applications Developers
Country: India
Interview Type: Phone Interview
@Dilbert Einstein
Won't heaps use O(n) extra space? Or is it possible to create max and min heap using the same input array?
If heaps require extra space, won't O(n) be a large number for extra space?
@Dilbert Einstein
I understand heap has better time complexity, just wanted to understand the space complexity. I'm not very familiar with heaps.
@Siva Chidambaram Somu
Few things:
1) Heap space complexity in this case is 3 and not n. I am only storing 3 solution candidate values in heap at any time, not entire array
2) We can just create heap on pointers instead of actual data itself (here data is just primitive integers so hard to see this advantage, but if we were dealing with large structs, we can just maintain heap of the pointers)
3) Trade off with alternate solutions a) To check the 3 values independently => does not scale b) To sort the elements - in place sorting is time complexity wise horrible performance
@Dilbert Einstein - there is one more case - the largest 3 nos include 1 -ve and 2 +ve values. so you have to scan the array multiple time.
@Vinod K
I think you misunderstood my algorithm (or misunderstood the problem - he is asking for maximum product, not maximum absolute value of product). I am separating positive values and negative values and then determining the largest values in each group. Please go through the solution I gave again. The case you are mentioning should not occur in the case of >3 elements.
If you still think there is an issue, give me a test input where my logic breaks and we can take our discussion from there.
Thanks!
for [-5,-10,1,2,3] it would give 1*2*3 => 6 as max_product while max_product is -5*-10*3 => 150
Killer input by Knuth, though Dilbert's solution can be extended to use a min-heap to store the top 3 +ve values(p1>=p2>=p3) and use a max-heap to store bottom 2 -ve values (n1<=n2). The max3 product can be computed as below:
if ( n1 * n2 > p1 * p2)
return n1 * n2 * p3
else
return p1 * p2 * p3
Hi All,
I can see four different cases for 3 numbers, + represents positive number and - reps negative number assuming numbers are sorted in decreasing order.
+ + + + + ...
+ + - - - ...
+ - - - - ...
- - - - - ...
For the first and third case direct multiplication of max 3 nos will do (i.e. a[0] a[1] a[2]).
For the second case if array size is > 3 we have to multiply the a[0] a[2] a[3]
For the fourth case we should use the first two numbers and the last number i.e. a[0] a[1] a[n-1]
We should return max of these three numbers which we calculated.
In all four cases we should make sure '0' is nor present.
Please let me know if there is anything wrong here.
-Arun
public static Integer maxProduct(Integer[] myarray){
Integer max,secondmax,thirdmax,min,secondmin,temp;
Integer maxproduct ;
if(myarray.length < 3){
return -1;
}
if(myarray.length == 3){
maxproduct = 0;
for(int i=0;i<myarray.length;i++){
maxproduct = maxproduct + myarray[i];
}
return maxproduct;
}
max = myarray[0];
secondmax = myarray[1];
thirdmax=myarray[2];
if(secondmax < thirdmax){
temp = secondmax;
secondmax = thirdmax;
thirdmax = temp;
}
if(max<secondmax){
temp = max;
max = secondmax;
secondmax = temp;
}
min = thirdmax;
secondmin = secondmax;
for(int i=3;i<myarray.length;i++){
if(myarray[i] > max){
secondmax = max;
max = myarray[i];
continue;
}
if(myarray[i] > secondmax){
thirdmax = secondmax;
secondmax = myarray[i];
continue;
}
if(myarray[i] > thirdmax){
thirdmax = myarray[i];
continue;
}
if(myarray[i] < min){
secondmin = min;
min = myarray[i];
continue;
}
if(myarray[i] < secondmin){
secondmin = myarray[i];
}
}
maxproduct = max*secondmax*thirdmax;
if( (min*secondmin*max) > maxproduct){
return (min*secondmin*max);
}
return maxproduct;
}
#include<stdio.h>
int main()
{int a[]={5,2,1,-4,3,8,6,5,-9};
int n=9;
int pass,i;
int temp;
for(pass=n-1;pass>=0;pass--)
{for(i=0;i<pass-1;i++)
{if(a[i]>a[i+1])
{temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;}}}
for(i=0;i<9;i++)
printf("%d\t",a[i]);
int maxprod;
}
max(a[0]*a[1]*a[n-1],a[n-3]*a[n-2]*a[n-1]);
#include<stdio.h>
int main()
{int a[]={5,2,1,-4,3,8,6,5,-9};
int n=9;
int pass,i;
int temp;
for(pass=n-1;pass>=0;pass--)
{for(i=0;i<pass-1;i++)
{if(a[i]>a[i+1])
{temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;}}}
for(i=0;i<9;i++)
printf("%d\t",a[i]);
int maxprod;
}
max(a[0]*a[1]*a[n-1],a[n-3]*a[n-2]*a[n-1]);
The logic is to sort the array regardless of positives and negatives,
perform the sanity checks like no of elements<3 return error, elements==3 then return the product, lastly if number of elements >3 then 1.sort them 2.take product of first two elements and last element and also product of last three elements
find maxmum of these two products and that will be max product; reason is that if all elements are positive then simply last three elements after sorting will give us the answer and if some of them are negative then product of first two elements of sorted array will either produce a negative answer or positive ( if both are negative the product will be positive and if one is negative then product is negative) in either case we will compare this product with product of last three elements and the greater of these two will be the maxproduct.
I 've tried it all positive case (-6,-5,4,6,9,11} and also (-6,4,7,8,9,11,13} and also (-6,0,1,4,5,7,8,11} this logic holds in all the above cases!
public static void test(){
int a[]= new int[]{ -1 ,3,7,-88,2,10,45,11,2,75,60};
int fMax= Integer.MIN_VALUE+2;
int sMax = Integer.MIN_VALUE+1;
int tMax = Integer.MIN_VALUE;
for(int i=0;i<a.length;i++){
if(a[i] > tMax && tMax < sMax && tMax < fMax){
tMax = a[i];
}else if(a[i] > sMax && sMax < fMax) {
sMax = a[i];
}else if(a[i] > fMax){
fMax = a[i];
}
}
System.out.println(" " + fMax + " " + sMax + " " + tMax);
System.out.println("MaxProduct " + (fMax*sMax*tMax));
}
Here is a tested O(n) algorithm:
public static int getMaxProduct(int[] a) throws IllegalArgumentException{
if(a==null||a.length<3)
throw new IllegalArgumentException();
if(a.length==3)
return a[0]*a[1]*a[2];
int[] min= new int[3];
min[0]=min[1]=min[2]=Integer.MAX_VALUE;
int[] max = new int[3];
max[0]=max[1]=max[2]=Integer.MIN_VALUE;
for(int i=0; i<a.length; i++){
for(int j=0; j<3; j++){
if(a[i]<min[j]){
//shift rest values
for(int k=2; k>j; k--){
min[k]=min[k-1];
}
min[j]= a[i];
break;
}
}
for(int j=0; j<3; j++){
if(a[i]>max[j]){
for(int k=2; k>j; k--){
max[k]=max[k-1];
}
max[j]= a[i];
break;
}
}
}
int product= Math.max(min[0]*min[1]*min[2], Math.max(max[0]*max[1]*max[2], min[0]*min[1]*max[0]));
return product;
}
int MaximumProduct(int * arr)
{
int * a = NULL;
int * b = NULL;
int * c = NULL;
int * d = NULL;
int * e = NULL;
for (int i =0 ; i < sizeof(arr)/sizeof(arr[0]); i++) {
if (arr[i] < 0) {
if (NULL == d) {
d = new int (a[i]);
}
else if (NULL == e) {
if (*d > a[i]) {
e = new int(*d);
*d = a[i];
}
else {
*e = arr[i];
}
}
else if (arr[i] < *d) {
*e = *d;
*d = arr[i];
}
else if (arr[i] < *e) {
*e = arr[i];
}
} // end of negative number check
else {
if (a!=NULL && b!=NULL && c!=NULL) {
if (arr[i] > *a) {
*c = *b;
*b = *a;
*a = arr[i];
}
else if (arr[i] > *b) {
*c = *b;
*b = arr[i];
}
else if (arr[i] > *c) {
*c = arr[i];
}
continue;
}
if (NULL == a) {
a = new int (arr[i]);
}
else if (NULL == b) {
if (arr[i] > *a) {
b = new int(a);
*a = arr[i];
}
}
else if (NULL == c) {
if (arr[i] > *a) {
c = new int(*b);
*b = *a;
*a = arr[i];
}
else if(arr[i] > b) {
c = new int(*b);
*b = arr[i];
}
else {
c = new int (arr[i]);
}
}
}
return ( (a*b)*c > (a*d)*e ? (a*b)*c : (a*d)*e);
}
Can't this be solved in O(n), only iterating the array twice?
step1 . try to find biggest 3 positive numbers in one iteration.
step2.
if there are biggest 3 positive numbers
try to find smallest 2 negative numbers in one iteration
return bigger one of biggest positive * two smallest negative and three biggest positive
if there are only one or two positive,
find two smallest negative and multiple with biggest positive
if there isn't any positive,
find three biggest negative or try to find 0.
In case sorting is allowed:
sort the array in ascending order
possible pattern we will get like below:
1. + + ........................ + + +
2. - - .......................... - - +
3. - - .......................... + + +
4. - - .......................... - + +
5. - + .........................+ + +
6. - - ......................... - - -
For 1st, 5th and 5th case product of last three number(most +ve) will be highest
For case 2nd and 4th product of most -ve two number and max positive number will be highest
For case 3 find [product of most -ve two number and max positive number] and [product of last three number(most +ve)] and which ever is max will be max in all.
private int MaxProduct(int[] arr) {
int maxProd=0;
int num1=0,num2=0, num3=0;
for(int i=0;i<arr.length-1;i++){
for(int j=i+1;j<arr.length;j++){
int prod=arr[i]*arr[j];
if(prod>maxProd){
maxProd=prod;
num1=arr[i];
num2=arr[j];//These nos num1 and num2 gives maximum product of 2 nos in arr
}
}
}
int prod=maxProd;
for(int i=0;i<arr.length;i++){
if(arr[i]!=num1&&arr[i]!=num2){
int temp=arr[i]*prod;
if(temp>maxProd){
maxProd=temp;
num3=arr[i];//this no give maximum product of 3 digit num1*num2*num3=maximum Product
}
}
}
System.out.println(num1);
System.out.println(num2);
System.out.println(num3);
return maxProd;
}
check this out::
int MaxTripleProduct(int arr[], unsigned int len)
{
switch(len)
{
case 0:
ASSERT(false);
break;
case 1:
return arr[0];
break;
case 2:
return arr[0] * arr[1];
break;
case 3:
return arr[0] * arr[1] * arr[2];
break;
default:
//sort array with 0(n) sorting algorigthm
countingSort(arr, len);
if (arr[len - 1] < 0)
{
return arr[0] * arr[1] * arr[2];
}
else
{
return max(arr[0] * arr[1], arr[len-3] * arr[len-2]) * arr[len - 1];
}
}
}
Depending on what we know about input, I have one solution if all values are positive and another solution if values can be negative.
- Dilbert Einstein May 12, 2013Case All positive:
--------------------
Do basic sanity checks.
check for array size:
<3 return error;
==3 return product of 3 values
> 3 : get the largest three values and return their product as answer
To get the largest 3 values, sorting is bad because of O(nlogn) complexity. Instead, initialize a min-heap array with first 3 values. Iterate through the rest of array, check each value against the top(min) value of heap, if current value is smaller, discard it but if greater then remove the min from heap and insert the current value. In the end you will have largest three in the heap. The complexity is O(n * log3). Using customized heap, we can reduce log3 as well.
Case Negative values are present:
-----------------------------------
Do basic sanity checks.
check for array size:
check for array size:
<3 return error;
==3 return product of 3 values
> 3 do two things:
1) Find largest three positive values - take their product say P1
2) Find largest (by absolute value) two negative values & one largest positve value - take their product P2
Then answer = Max (P1, P2);
The idea is, two negative values when multiplied gives positive value. Since we have three, we need to check for possibility of two negative and one positive combination.
NOTE: Handle edge cases when 1) & 2) cannot happen: e.g. if all are negative values in the array, then take product of 3 smallest (by absolute) negative values.