Amazon Interview Question Software Engineer in Tests
Country: India
Interview Type: Phone Interview
It's not necessary to sort the array just to find the largest 3 positive numbers and the largest negative number.
No need to sort!
Maintain a minheap of 3 elements based on absolute values. height of this will always be 1
Complexity O(n)
@bhupendra : I agree this can be done without sorting. But there will be so many cases that it won't suffice to keep a minheap of height 3.
Eg input : -100, 12, 42, 89, 103
How will your logic work here?
Sorry I missed one condition!
After forming the heap once, If incoming element is larger than root replace!
In your example! Below is the heap formation and you need to compare only absolute values . -100 is converted to 100
------------
12
100 42
-----------
42
100 89
------------
89
100 103
----------
@incognitosj
I think we need to do some more modification to above approach!
1. We need to maintain number of negative nodes inserted.
2. We need to keep track of greatest positive number from those inserted or deleted from the heap at any point of time.
say max.
In the final heap if number of -ve numbers is odd use the max from above along with other two positive nuumber
else you have the solution.
Note: Original numbers will be inserted in the heap with proper sign just comparison while inserting will be based on absolute values
In the above example:
Number of odd numbers in final heap is odd so we will discard the negative number and calculate product using other two and max (42)
Please comment if any error!
@bhupendra: One more case needs to be taken care of, where all the integers are less than 0. Then some more modification is needed.
I have considered that case!
When the numbers of negative numbers are odd you will discard the number with minimum absolute value and use max instead
actually in case the integers are negative, it should use the minimum absolute value.
Eg: -10, -90, -9, -56, -32
answer should be (-9)*(-10)*(-32) and not (-90)*(-56)*(-32)
The solution involves in finding three maximum and two minimum numbers. If the minimum numbers are negatives and if their product is greater than the two maximum number's product, then they have to considered for maximum product.
I don't think "the largest 3 numbers" is the right solution, the numbers may be negative, right? two negative numbers' product is still positive. Look at the following example:
6 3 2 -100 -101
The first 3 number is 6 3 2, the product = 36. But the largest product here should be 6 * -100 * -101.
I think you are right.
and I think we should first find 6 numbers:the max 3 positive and the max 3 negitive.
the 3 number must in this 6 numbers...
@kurskk141, this solution is still not perfect, we still need to figure out the min 3 negative. So the solution must be in max 3 positive, max 3 negative and min 3 negative. Of course the length of the array should be larger than 9.
One thing for sure that we have to find the max positive number first. Then we can find the max 2 positive number and max 2 negative number besides it. Compare the two product to get the maximum.
What if there are no positive numbers. The product in that case shall be the min product.
This had so many cases i ended up hardcoding a lot. Let me know if this can be improved.
Some code:
Test cases:
1) has less than 3 elements
2) has only 3 elements;
3) has all zeroes
4) has less than 3 positive +negative numbers
5) has atleast 3 positive 2 negative
6) has atleast 2 positive 3 negative
7) has atleast 1 postive and 3 negative
int Find_maxProduct(int A[n])
{
MinHeap minHeap;//has all Max values
MaxHeap maxHeap;// has all min values
if(n<3) return -1;
if(n==3) return A[0]*A[1]*A[2];
bool hasZero;
for(int i=0; i<n-1; i++)
{
if(A[i]==0) {hasZero=true; continue;}
if(i<3)
{
minHeap.push(A[i]);
maxHap.push(A[i]);
continue;
}
if(A[i]>0 && A[i]>minHeap.top())
{
minHeap.pop();
minHeap.push(A[i]);
}
if(A[i]<0 && A[i]<maxHeap.top())
{
maxHeap.pop();
maxHeap.push(A[i]);
}
}
int prod_pos=1;
int prod_neg=1;
int max;
if(minHeap.size()+maxHeap.size()<3)
{
return (hasZero)?0; -1;
}
if(minHeap.size()==3)
{
prod_pos*=minHeap.top(); minHeap.pop();
prod_pos*=minHeap.top(); minHeap.pop();
max= minHeap.top();
}
if(minHeap.size()==2)
{
prod_pos=0;
minHeap.pop();
max=minHeap.top();
}
if(minHeap.size()==1)
{
prod_pos=0;
max=minHeap.top();
}
if(maxHeap.size()==3)
{
maxHeap.pop();
prod_neg*=maxHeap.top(); maxHeap.pop();
prod_neg*=maxHeap.top(); maxHeap.pop();
}
if(maxHeap.size()==2)
{
prod_neg*=maxHeap.top(); maxHeap.pop();
prod_neg*=maxHeap.top(); maxHeap.pop();
}
return max* MAX( prod_pos, prod_neg);
}
O(n log3 = n) time and O(3) space:
use a min heap of length 3. So while traverse the arr check each element if is bigger than the min in the heap and if so remove the min and add the new one. At the end we will have the max elements which you can do the product
Here is a sample Java code:
private final static int NUMS = 3;
public int maxProduct(int[] arr) {
int result = arr.length > 0 ? 1 : 0;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < arr.length && i < NUMS; i++)
pq.add(arr[i]);
for (int i = NUMS; i < arr.length; i++)
if (pq.peek() < arr[i]) {
pq.poll();
pq.add(arr[i]);
}
while (pq.size() > 0)
result *= pq.poll();
return result;
}
just saw the "jilong.liao" who has a point.
So if there are negative values we can do max heap of len 3 to keep the min values (just the same logic as the min heap).
Then we remove the first element from the max heap and return Math.Max("maxHeap.poll() * maxHeap.poll() * minHeap.peek()", "minHeap.poll() * minHeap.poll() * minHeap.poll()")
we still keep the Linear time and constant space
public class Prod{
public static void main(String[] arg)
{
int[] arr={4,3,6,2,1,8};
int len_arr=arr.length;
for(int i=0; i<len_arr; i++)
{
for(int j=1; j<(len_arr-i); j++)
{
if(arr[j-1]>arr[j])
{
int temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
}
int product = arr[arr.length-1]*arr[arr.length-2]*arr[arr.length-3];
System.out.println(product);
I try to write C++ codes for this question;
#include <iostream>
using namespace std;
int main()
{
int array[] = {10, 60, 40, 0, -1, -60, -50, 200};
int n=sizeof(array)/sizeof(int);
cout<<"Before sorted: "<<endl;
for (int i=0; i<n; i++)
cout<< array[i] << " ";
int tmp;
for (int i=0; i<n-1; i++)
for (int j=0; j<n-1-i; j++)
if (array[j]<array[j+1])
{
tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
}
cout<<"\n\nAfter sorted: "<<endl;
for (int i=0; i<n; i++)
cout<< array[i] << " ";
cout<<endl;
int maxproduct1;
int maxproduct2;
maxproduct1=array[0]*array[n-2]*array[n-1];
maxproduct2=array[0]*array[1]*array[2];
cout<< "\nThe maxproduct of 3 numbers\n"<<(maxproduct1>maxproduct2?maxproduct1:maxproduct2)<<endl;
return 0;
}
This question seem simple, but is actually tricky. I think Yoda's answer is the closest here. What you want to do is breakdown the possible scenarios:
1) Positive Numbers >= 3
a) No Negatives in array: Answer is just the product of the three max numbers.
b) 2 or more Negatives: Calculate the product of two maximum negative numbers and the maximum positive number, and compare to above to find Answer
2) Positive Numbers == 2
a) 1 Negative Number in array: Answer is just the product of the two positive numbers and the negative number
b) 2 or more Negatives: Answer is the product of two maximum negative numbers and the maximum positive number
3) Positive Numbers == 1
a) Answer is the product of two maximum negative numbers and the positive number
4) Positive Numbers == 0
a) Answer is the product of the MINIMUM negative numbers.
So you want to keep track of the 3 Max Positive, 3 Max Negative, and 3 Min Negative numbers to solve this problem. You can utilize 3 arrays to track these, or 3 Max/Min Heaps to track these. If you use an array of size 3 so that the numbers you're tracking are limited, you'll save a little bit of speed and memory compared to tracking all the numbers in a Heap (Heap insertion = O(log n)).
The algorithm is basically traverse through the array and keep track of the above numbers, and then find the max product by doing the multiplications based on the scenario above.
My C code: pastie.org/4410410
following cases(assuming atleast 3 elements exist in an array) after sorting in nlog(n) in increasing order, If sign of last three elements are
case1) - - - than answer is product of last three numbers
case 2)if sign is - + + than answer is min{product of last two num; product of first two num}*third max
case 3)if sign is - - + product of first two min num*last num of array
case 4)if sign is + + + ans is last num*max{product of first two num; product of second and third last num}
public class MaxThreeProduct {
public static void main(String a[]){
System.out.println("Enter the array");
int no[] = {-45,-98, -4, -78, -9, -90, 10};
int largestNo =Integer.MIN_VALUE, largerNo=Integer.MIN_VALUE, largeNo=Integer.MIN_VALUE;
for(int i=0; i<no.length;i++){
if(no[i]>largeNo && no[i]<largerNo){
largeNo=no[i];
}
else if(no[i]>largerNo && no[i]<largestNo){
largeNo=largerNo;
largerNo = no[i];
}
else if(no[i]>largestNo){
largeNo = largerNo;
largerNo = largestNo;
largestNo = no[i];
}
}
System.out.println("Largest : "+largestNo);
System.out.println("Larger : "+largerNo);
System.out.println("Large : "+largeNo);
System.out.println("Max Product is : "+largeNo*largerNo*largestNo);
}
}
import java.util.Arrays;
public class MaxProductOfThreeNumberTest {
public static void main(String[] args){
int[] Arr={-25,-1,1,2,3,7,20};
int MaxProduct=0;
quickSort(Arr,0,Arr.length-1);
System.out.println(Arrays.toString(Arr));
if(Arr.length==3){
MaxProduct=Arr[0]*Arr[1]*Arr[2];
}
else if(Arr.length>3){
if((Arr[0]<0)&&(Arr[1]<0) ){
if((Arr[0]*Arr[1])> (Arr[Arr.length-3]*Arr[Arr.length-2])){
MaxProduct=Arr[0]*Arr[1]*Arr[Arr.length-1];
}
else{
MaxProduct=Arr[Arr.length-3]*Arr[Arr.length-2]*Arr[Arr.length-1];
}
}
}
if(Arr.length>=3){
System.out.println("MaxProduct :"+MaxProduct);
}
else{
System.out.println("Array lenght should be equal or greater than 3");
}
}
private static int partition(int[] list, int first, int last) {
int pivot = list[first];
int low = first + 1;
int high = last;
while (high > low) {
while (low < high && list[low] < pivot) {
low++;
}
while (low < high && list[high] >= pivot) {
high--;
}
if (high > low) {
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && list[high] >= pivot) {
high--;
}
if (pivot > list[high]) {
list[first] = list[high];
list[high] = pivot;
return high;
} else {
return first;
}
}
private static void quickSort(int[] list, int first, int last) {
if (last > first) {
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
}
1. Sort the array
- incognitosj July 17, 20122. If minimum integers is greater than 0, product of maximum 3 integers is the answer.
3. If there exist at least 2 integers less than 0, find the product of mimimum 2 integers and 1 max integers. Compare it with the product of 3 maximum integers. Greater of the two is the answer.
Eg:
Given array : 10, 67, 28, 0, -1, -30, -20
sorted form : -30, -20. -1, 0, 10, 28, 67
product of 3 max integers : 10*28*67 = 18760
product of 2 min integers and 1 max int = (-30)*(-20)*67 = 40200
Answer : 40200