Amazon Interview Question Software Engineer in Tests
Country: United States
in second traverse why you want to find minimum numbers? you need to find max product right? can you give an example?
What's the point in taking a linked list when we can actually store the three largest numbers in simple variables
Let the three largest number be m1,m2,m3 and the lowest number be l1,l2
then
{
if(l2*l1>m1*m2)
printf("%d ",l1*l2*l3);
else if (m1<0) // for all negative numbers
printf("%d",m1*m2*m3);
else
printf("%d ",l1*m1*m2);
}
this code will work for all test cases
i) All negative numbers
ii) All positive numbers
iii) single negative number
iv) mixture of -ve and +ve numbers
One traversal should be enough!! maintain three variables to store (the max prod of two numbers so far, and min negative product of numbers seen so far, and check if we can make max products including the current number with the above said number) Traverse till the last.. You get the max product, Done!!
#include<stdio.h>
int max(int a,int b)
{
return a>b?a:b;
}
int prod(int a[],int n)
{
int min1,min2,max1,max2,max3;
min1=min2=32767;
max1=max2=max3=-32767;
int i;
for(i=0;i<n;i++)
{
if(a[i]>max1)
{
max3=max2;max2=max1;max1=a[i];
}
else if(a[i]>max2)
{
max3=max2; max2=a[i];
}
else if(a[i]>max3)
max3=a[i];
if(a[i]<min1)
{
min2=min1; min1=a[i];
}
else if(min2>a[i])
min2=a[i];
printf("%d %d %d %d %d\n",max1,max2,max3,min1,min2);
}
if(min1<0 && min2 <0)
return max(min1*min2*max1, max1*max2*max3);
else
return max1*max2*max3;
}
int main()
{
int a[]= {8,4,3,5,2,-1,-9,-10,11};
printf("%d\n",prod(a,9));
return 0;
}
To get a positive result from 3 numbers, you need either 3 +ve numbers, or 2 -ve and 1 +ve. So, first we check if the size is > 3, and if it is, sort the array. We know we need the rightmost number so we save it. We then compare the product of 2 leftmost, or the 2 rightmost-1. Whichever is bigger, we take.
So let's say our initial array is:
{-25,1,-1,3,20,7,2}
We sort it:
{-25,-1,1,2,3,7,20}
We need 20 for either scenario so we keep it. We then compare
-25 * -1 = 25
3 * 7 = 21
Because 25 > 21, we keep -25 and -1.
Our result is -25, -1, 20. Time is sorting time so say O(n log n).
Dont know how Kadane is applicable here. It can be done simply by sorting and then multiplying max numbers accounting for signs.
Dont know how Kadane is applicable here. It can be done simply by sorting and then multiplying max numbers accounting for signs.
Well this can be solved in,O(n) time,
Here is my solution,
Traverse the array, and maintain a linked list of size three ,that stores the three largest elements this takes O(n) time.
Now again traverse the array and find the two minimum numbers O(n) time
Now multiply the elements of linkedlist store it as max sum , and compare it with product of two -ve numbers and every element of the maintained linked list
return the highest product...
This works in O(n)
hey did u mean linked-list or BST coz to identify three largest number from an array using list would not take O(n)...but if we go with BST extreme right and its parent and grand parent will become the 3 largest number and similarly we would b able to find the 2 smallest number.
If i m making any mistake pls do correct me.
Thanks :)
can be solved using dynamic programming using only one pass
Let the given array be A. While passing the A from left to right, construct a new array P and keep track of 3 variables x,y,z of whose product is the maximum.
while passing through A , suppose we are at position i , then
P[i] = max product of 3 numbers (x,y,z) which lie in between between A[0] to A[i]
when extending the solution to i+1,
P[i+1] = max(P[i], P[i] * A[i+1]/x , P[i] * A[i+1]/y, P[i] * A[i+1]/z)
In each of the later 3 cases, x or y or z will be replaced with A[i+1]
Finally P[n-1] contains max product of 3 numbers of A.
public static void maxProdOf3Nos(long[] a){
long M1,M2,M3,m1,m2;
if(a.length<3) return ;
M1=a[0];M2=a[1];M3=a[2];
m1=a[0];m2=a[1];
long t=0;
if(M1<M2){
t=M2; M2=M1;M1=t;
}if(M1<M3){
t=M3;M3=M1;M1=t;
}
if(M2<M3){
t=M3;M3=M2;M2=t;
}
if(m1>m2){t=m2;m2=m1;m1=t;}
System.out.println(M1+" "+M2+" "+M3);
for(int i =3;i<a.length;i++){
if(M1<a[i]){
M3=M2;
M2=M1;
M1=a[i];
}else if(M2<a[i]){
M3=M2;
M2=a[i];
} else if(M3<a[i]){
M3=a[i];
}
if(m1>a[i]){
m2=m1;m1=a[i];
}else if (m2>a[i]) m2= a[i];
}
System.out.println(M1+" "+M2+" "+M3+" "+m1+" "+m2);
double prod = M1*M2*M3>M1*m1*m2 ?M1*M2*M3:M1*m1*m2;
System.out.println("Max Product = "+prod);
}
int array[]={9,4,1,2,-5,-7}; //-7,-5,2,1 ,4,9
int min;
int second_min;
int max;
min=array[0];
second_min=array[1];
max=array[0];
for(int i=1;i<array.length;i++)
{
if(array[i]<min)
{
second_min=min;
min=array[i];
}
if(array[i]>max)
max=array[i];
}
System.out.println((min*second_min*max));
}
Yes, that will no work if all numbers in the array are negative.
But this one will:
max = secondmax = thirdmax = 0;
min = secondmin = 0;
for( int i = 1; i < n; i++ )
{
candidate = i;
if( a[candidate] >= a[max] )
swap( secondmax, thirdmax );
swap( max, secondmax );
swap( candidate, max );
else if( a[candidate] >= a[secondmax] )
swap( secondmax, thirdmax );
swap( candidate, secondmax );
else if( a[candidate] > a[thirdmax] )
thirdmax = candidate;
candidate = i;
if( a[candidate] <= a[min] )
swap( min, secondmin );
swap( candidate, min );
else if( a[candidate] < a[secondmin] )
secondmin = candidate;
}
if( thirdmax == 0 )
return 0; // there are less than three elements in the array
return( a[max]*a[secondmax]*a[thirdmax], a[max]*a[min]*a[secondmin] );
I think it wont work 2 please check for input -2,-3,-4,-5, output should be - 24 correct me if i am wrong
I think it wont work 2 please check for input -2,-3,-4,-5, output should be - 24 correct me if i am wrong
I think it wont work 2 please check for input -2,-3,-4,-5, output should be - 24 correct me if i am wrong
I will simply follow the algorithm..
while(number_of_element>=6)
{
arrayleast[3];
arraymax[3];
}
Once the complete array is traversed, simply multiply each element in a list with other numbers forming pairs of 3.
SO we have total 6*5*4 operations. and find the maximum of those . numbers involved in it are our answer.
A naive python implementation: didn't check for many input values. but hope few changes will be required.
#lis = [1,4,2,-4,10,7,-10,20,-30,-20]
lis =[10,10,-10,10,-20,-30,30,20]
mx1=0
mx2=0
mx3=0
mn1=0
mn2=0
for i in lis:
if i>mx1:
mx3=mx2
mx2=mx1
mx1=i
if i>mx2 and i<mx1:
mx3=mx2
mx2=i
if i>mx3 and i<mx2:
mx3=i
if i<mn1:
mn2=mn1
mn1=i
if i<mn2 and mn1<i:
mn2=i
if (mx1*mx2*mx3) > (mx1*mn1*mn2):
print mx1,' ',mx2,' ',mx3
else:
print mx1,' ',mn1,' ',mn2
Take two arrays a[2] and b[3]
Traverse the list and check for each element if it is >0 then call Max(b) else Min(a), these functions would internally check for elements in the array and sorts them in the array.
finally when all the processing is done, just multiply max element of b with all the elements of a and all the elements of b, whichever is greater is the solution. :)
Another solution can be which is in order(N) complexity.
1. Traverse the array keep track of (three max number max1 max2 max3) along with the track of two minimum numbers (min1 min2) at the end take product of max2 and max3 also product of min1 and min2. check the greater product value and you will have three numbers.
/* Here is my code in O(n) time. I think it works fine.. Inform if any test case fails or error in code*/
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i, max1, max2 , max3, min1, min2, min3, A[9] = { 4, 1, -3, 4, -1, 2, 4, -5, 4 };
max1 = 0; max2 = 0; max3 = 0;
min1 = 0; min2 = 0;
for(i = 0; i < 9; i++)
{
if(A[i] >= max1)
{
max3 = max2;
max2 = max1;
max1 = A[i];
}
if(A[i] <= min1)
{
min2 = min1;
min1 = A[i];
}
}
int p_mul = max2 * max3;
int n_mul = min1 * min2;
// printf("%d %d %d %d %d\n",max1,max2,max3,min1,min2);
if(p_mul > n_mul)
printf("%d", p_mul * max1);
else
printf("%d", n_mul * max1);
system("pause");
return 0;
}
//O(n) soln
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i, max1, max2 , max3, min1, min2, min3, A[9] = { 4, 1, -3, 4, -1, 2, 4, -5, 4 };
max1 = 0; max2 = 0; max3 = 0;
min1 = 0; min2 = 0;
for(i = 0; i < 9; i++)
{
if(A[i] >= max1)
{
max3 = max2;
max2 = max1;
max1 = A[i];
}
if(A[i] <= min1)
{
min2 = min1;
min1 = A[i];
}
}
int p_mul = max2 * max3;
int n_mul = min1 * min2;
// printf("%d %d %d %d %d\n",max1,max2,max3,min1,min2);
if(p_mul > n_mul)
printf("%d", p_mul * max1);
else
printf("%d", n_mul * max1);
system("pause");
return 0;
}
public static int getMaxProduct(int array[]) {
int max1 = Integer.MIN_VALUE;
int max2 = max1, max3 = max1;
int min1 = Integer.MAX_VALUE, min2 = min1;
for (int i = 0; i < array.length; i++) {
if (array[i] > max1) {
max2 = max1;
max1 = array[i];
}else if(array[i]>max2){
max3 = max2;
max2 = array[i];
}else if(array[i]>max3){
max2 = array[i];
}
if (array[i] < min1) {
min2 = min1;
min1 = array[i];
}else if(array[i]<min2){
min2 = array[i];
}
}
System.out.println("max1 = " + max1 + " max2 = " + max2 + " max3 = "
+ max3);
System.out.println("min1 = " + min1 + " min2 = " + min2);
return max1*max2*max3>max1*min1*min2?max1*max2*max3:max1*min1*min2;
}
if size of input < 3, return error
if size of input is 3, reutrn axbxc
else
positivesList = three largest elems if they are positive..
negativeList = two smallest elems if they are negative..
if size of positivesList == 0
splnegativeList = three largest elems; return product of these three
if size of positiveList < 3
return product of 1 highest +ve numeber and 2 least -ve numbers
if size of negativeList < 2
return product of 3 +ve numbers
if size of negativeList is 2 and positiveList is 3
return maxOf(product of positives , product of highest positive number and two negative numbers)
#include<stdio.h>
int main()
{
int arr[]={-1,-5,-2,-6,2,5,3,1,9};
int temp,i,j,k,l,total,max,len;
len = sizeof(arr)/sizeof(int);
for(i=0;i<len;i++)
{
for(j=0;j<len-1;j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
max=(arr[len-1]*arr[len-2]*arr[len-3]);
if(arr[0] && arr[1] < 0)
{
k=-arr[0];
l=-arr[1];
}
if(((k>=arr[len-2]) && (l>=arr[len-2])))
{
max = (arr[len-1]*k*l);
}
printf("Maxinum:%d",max);
}
#include<stdio.h>
int main()
{
int arr[]={-1,-5,-2,-6,2,5,3,1,9};
int temp,i,j,k,l,total,max,len;
len = sizeof(arr)/sizeof(int);
for(i=0;i<len;i++)
{
for(j=0;j<len-1;j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
max=(arr[len-1]*arr[len-2]*arr[len-3]);
if(arr[0] && arr[1] < 0)
{
k=-arr[0];
l=-arr[1];
}
if(((k>=arr[len-2]) && (l>=arr[len-2])))
{
max = (arr[len-1]*k*l);
}
printf("Maxinum:%d",max);
}
import java.util.Arrays;
/*Given an array of N integers with +ve & -ve numbers. Find the maxproduct of 3 numbers ? & Test Cases*/
public class Q4 {
int maxProduct(int[] numbers) {
Arrays.sort(numbers);
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
int left = numbers[0] * numbers[1] * numbers[numbers.length - 1];
int right = numbers[numbers.length - 1] * numbers[numbers.length - 2]
* numbers[numbers.length - 3];
int[] max = { left, right };
Arrays.sort(max);
System.out.println("Max = " + max[max.length - 1]);
return 0;
}
public static void main(String[] args) {
int[] numbers = { 2, 5, 6, 1, 3, 0, -6, -2 };
int[] numbers1 = { -8, 2, 5, 6, 1, 3, 0, -6, -2 };
int[] numbers2 = { 2, 5, 6, 1, 3, 6, 3 };
int[] numbers3 = { -2, -5, -6, -1, -3, -6, -3 };
int[] numbers4 = { 2, 5, 6, 1, 3, -6 };
int[] numbers5 = { 2, 6, 1, 3, 0, -6, -2 };
Q4 q4 = new Q4();
q4.maxProduct(numbers);
q4.maxProduct(numbers1);
q4.maxProduct(numbers2);
q4.maxProduct(numbers3);
q4.maxProduct(numbers4);
q4.maxProduct(numbers5);
}
}
// Test
// A. no number 0:
// 1. all +ve. --right is max.
// 2. all -ve. --right is max.
// B. have number 0:
// 3. 0 is on the left, and have >=2 -ve. --right or (2 left multiply 1 right)
// is max.
// 4. 0 is on the right, have <=2 +ve. --right(0) or (2 left multiply 1 right)
// is max.
the only combination to have a max product is having combinations has +++ and --+
my idea is to create two arrays ppp[3] and pnn[3]
step 1)
fill the first 3 positives number of the given array in ppp[3] from left and 1 positive and 2 negative numbers from left of the given array in pnn[3].
step 2)
now start traversing from the left if
a[0] >0 then check if a[0] is greater than any of the 3 elements in ppp, if it is then replace the lowest digit in ppp with a[0] and also check if a[0]> pnn[0](the ONLY positive number in pnn) if yes then replace pnn[0] with a[0].
if a[0]<0
then check if a[0]<pnn[2] OR a[0]<pnn[1] if any of the two are true then replace the larger of p[1] and p[2] with a[0]
step3) and repeat step 2 with a[i] increasing the i each time
step 3) compute the max of (ppp[0]*ppp[1]*ppp[2] and pnn[0],pnn[2],pnn[1]
public static int maxProduct(int a[],int max[],int number,int prod){
int index=0;
for(int i=0;i<a.length;i++){
if(Math.abs(a[i])>max[number -1]){
max[number-1] = Math.abs(a[i]);
index = i;
}
}
a[index] = 0;
prod *= max[number-1];
if(number-1 == 0 ){
return prod;
}
return maxProduct(a,max,number-1,prod);
}
public static void main(String[] args){
//int[] a = {-5, -7, 4, 2, 1, 9 };
int[] a = {-5, -7, 4,-8,9,1 };
int []max = {0,0,0};
int maxProduct = maxProduct(a,max,3,1);
System.out.println(maxProduct);
}
Well this can be solved in,O(n) time,
- vips February 28, 2012Here is my solution,
Traverse the array, and maintain a linked list of size three ,that stores the three largest elements this takes O(n) time.
Now again traverse the array and find the two minimum numbers O(n) time
Now multiply the elements of linkedlist store it as max sum , and compare it with product of two -ve numbers and every element of the maintained linked list
return the highest product...
This works in O(n)