Cloudera Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
Why abe? what if a and b are positive and e is negative?
Also, will this implementation work?
inputlist = [1,-4,-5,1,3,2]
mylist = [0,0,0,0,0]
for candidate in inputlist:
if(candidate>=mylist[0]):
mylist[2] = mylist[1]
mylist[1] = mylist[0]
mylist[0] = candidate
elif(candidate>=mylist[1]):
mylist[2] = mylist[1]
mylist[1] = candidate
elif(candidate>=mylist[2]):
mylist[2] = candidate
elif(candidate<=mylist[4]):
mylist[3] = mylist[4]
mylist[4] = candidate
elif(candidate<=mylist[3]):
mylist[3] = candidate
print(max((mylist[0]*mylist[1]*mylist[2]),(mylist[0]*mylist[3]*mylist[4])))
1) Find top 3 and bottom 2 values from the list in O(n)
2) Let the list be [a, b, c ..... d, e]
modification:
3) find maximum of b*c and d*e.
prod1 = max(b*c, d*e);
4. output: a * prod1.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MaxProduct
{
public class ProductResult
{
public int a { get; set; }
public int b { get; set; }
public int c { get; set; }
public long product
{
get
{
return a * b * c;
}
set{}
}
}
class Program
{
private static int length = 0;
private static List<int> Numbers;
private static List<ProductResult> Prods;
private static ProductResult Prod;
static void Main(string[] args)
{
while (true)
{
Numbers = new List<int>();
Prods = new List<ProductResult>();
System.Console.WriteLine("How many numbers would you like to enter ?");
length = int.Parse(System.Console.ReadLine().ToString());
System.Console.WriteLine("Enter the numbers : ");
for (int n = 0; n < length; n++)
{
Numbers.Add(int.Parse(System.Console.ReadLine().ToString()));
}
for (int m = 0; m < length; m++)
{
for (int n = 0; n < length; n++)
{
if (n == m) continue;
for (int o = 0; o < length; o++)
{
if (o == n || o == m) continue;
Prod = new ProductResult();
Prod.a = Numbers[m];
Prod.b = Numbers[n];
Prod.c = Numbers[o];
Prods.Add(Prod);
}
}
}
System.Console.WriteLine("The Maximum Product is : " + Prods.OrderByDescending(m => m.product).FirstOrDefault().product.ToString());
Console.ReadLine();
Console.Clear();
}
}
}
}
This seems to be much cleaner
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
}
This seems to be much cleaner:
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
}
public static void main(String[] args) {
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
}
Here's a simple O(n) solution in Python:
def highestPosProduct(arr):
if len(arr) < 3: return None
a = quickselect(arr, len(arr) - 1)
b = quickselect(arr, len(arr) - 2)
c = quickselect(arr, len(arr) - 3)
d = quickselect(arr, 1)
e = quickselect(arr, 0)
return max(a * b * c, a * b * e, a * d * e)
public int[] getHighestPositiveProduct(int[] input) {
// Largest keys (ignoring positive/negative aspect) will return largest positive product.
int[] largestKeys = {0, 0, 0};
// There can be only two negative keys, or it will return negative.
int negatives = 0;
for (int i = 0; i < input.length; i++) {
if (Math.abs(input[i]) > Math.abs(largestKeys[0])){
largestKeys[2] = largestKeys[1];
largestKeys[1] = largestKeys[0];
largestKeys[0] = input[i];
if (input[i] < 0) {
negatives++;
}
} else if (Math.abs(input[i]) > Math.abs(largestKeys[1])) {
largestKeys[2] = largestKeys[1];
largestKeys[1] = input[i];
if (input[i] < 0) {
negatives++;
}
} else if (Math.abs(input[i]) > Math.abs(largestKeys[0])) {
largestKeys[2] = input[i];
if (input[i] < 0) {
negatives++;
}
}
if(negatives != 2 && negatives != 0) {
continue;
}
}
return largestKeys;
}
Above code doesn't work for {-10,-9,-11,1, 3, 5, 2, 8, 0, -1, 3} test data
It gives O/P as : -990
This will work. I feel that the question is incomplete. It should specify what to return when all numbers are negative. Since in that case the product will not be positive, which is mentioned in the question - "Maximum positive product". Anyways, the below code works fine for all other situations except for these two
1. All numbers negative.
2. Array of size 3 with 1 negative number.
/**
* Find the maximum positive product of three distinct numbers in an array when
* sorting is not allowed.
*
* @author shivam.maharshi
*
*/
public class MaxPositiveProduct {
public static int get(int[] a) {
int m1 = Integer.MIN_VALUE, m2 = m1, m3 = m2;
int n1 = Integer.MAX_VALUE, n2 = n1;
for (int i = 0; i < a.length; i++) {
if (a[i] > m1) {
m1 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] > m2 && a[i] != m1) {
m2 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] > m3 && a[i] != m1 && a[i] != m2) {
m3 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] < n1) {
n1 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] < n2 && a[i] != n1) {
n2 = a[i];
}
}
return m1 * Math.max(m2 * m3, n1 * n2);
}
public static void main(String[] args) {
int[] a = new int[] { -10, -9, -11, 1, 3, 5, 2, 8, 0, -1, 3 };
System.out.println(MaxPositiveProduct.get(a));
}
}
I dont think its thats complicated. Following is my code with O(n).
package cc.cloudera.highestproduct;
public class HighestProductFinder {
public static void main(String[] args) {
// TODO Auto-generated method stub
int intArray[] = { 1, -2, -2, -4, 2, 0 };
int product, largestNeg, negCount;
product = 0;
negCount = 0;
largestNeg = 0;
for (int i = 0; i < intArray.length; i++) {
if (intArray[i] == 0) {
continue;
} else {
if (product == 0) {
product = intArray[i];
} else {
product *= intArray[i];
}
if (intArray[i] < 0) {
negCount++;
if (largestNeg == 0) {
largestNeg = intArray[i];
} else {
largestNeg = largestNeg > intArray[i] ? largestNeg : intArray[i];
}
}
}
}
if (negCount != 0 && negCount % 2 != 0) {
product /= largestNeg;
}
System.out.println("Max Product: " + product);
}
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
void swap_all(int &f,int &s,int &t)
{
if(f<s)std::swap(f,s);
if(f<t)std::swap(f,t);
if(s<t)std::swap(s,t);
}
int main()
{
int a[]={0, -1, 3, 100, -70, -5};
int i,f,s,t;
f=abs(a[0]);
s=abs(a[1]);
t=abs(a[2]);
swap_all(f,s,t);
for(i=3;i<6;i++)
{
if(t<abs(a[i]))
{
t=abs(a[i]);
swap_all(f,s,t);
}
}
std::cout<<"Highest product: "<<f*s*t<<"\n";
}
public class HighestProductCombination {
public static int highestProd(int[] input){
int prod = 0;
for(int i =0; i < input.length ; i++ ){
for(int j = i + 1; j < input.length ; j++ ){
for(int k = j + 1; k < input.length ; k++ ){
if(input[i]*input[j]*input[k] > prod){
prod = input[i]*input[j]*input[k];
}
}
}
}
return prod;
}
public static void main(String[] args) {
int a[]={0, -1, 3, 100, -70, -5};
System.out.println("higest prod of input " + highestProd(a) );
}
}
public static void main (String[] args){
int[] arr = new int[]{3,1,-2,4,-1};
System.out.println(hp(arr));
}
private static long hp (int[] arr){
if(arr.length < 3){
throw new RuntimeException("Invalid data set size");
}
int[] largest = new int[]{Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE};
for(int a:arr){
if(a > largest[0]){
largest[2] = largest[1];
largest[1] = largest[0];
largest[0] = a;
}
else if (a > largest[1]) {
largest[2] = largest[1];
largest[1] = a;
}
else if (a > largest[2]) {
largest[2] = a;
}
}
return largest[0]*largest[1]*largest[2];
}
private int getMaximumhighestnumbersproduct(int[] input){
int[] out = new int[5];
int[] index = new int[2];
int retval;
index[0] = gethighestnumindex(input, index);
out[0] = input[index[0]];
index[1] = gethighestnumindex(input, index);
out[1] = input[index[1]];
out[2] = input[gethighestnumindex(input, index)];
index[0] = getLowestnumindex(input, index);
out[3] = input[index[0]];
index[1] = getLowestnumindex(input, index);
out[4] = input[index[1]];
retval = out[1]*out[2];
if(out[3]*out[4] > retval){
retval = out[0]*out[3]*out[4];
}else{
retval = out[0]*retval;
}
return retval;
}
private int gethighestnumindex(int[] input, int[] indextoskip){
int ival = 0;
while((ival == indextoskip[0]) || (ival == indextoskip[1]) ){
ival++;
}
for(int i=0; i<input.length; i++){
if((indextoskip[0] != i) && (indextoskip[1] != i)){
if(input[ival] <= input[i]){
ival = i;
}
}
}
return ival;
}
private int getLowestnumindex(int[] input, int[] indextoskip){
int ival = 0;
while((ival == indextoskip[0]) || (ival == indextoskip[1]) ){
ival++;
}
for(int i=0; i<input.length; i++){
if((indextoskip[0] != i) && (indextoskip[1] != i)){
if(input[ival] >= input[i]){
ival = i;
}
}
}
return ival;
}
#include<stdio.h>
int main()
{
int a[] = {1, 4, -10, 2, -3};
int sum =0, large=0;
int size = sizeof(a)/4;
int i =0, j=0, k =0;
if(size < 3)
return 0;
else if(size == 3)
return (a[0] * a[1] * a[2]);
for( i = 0 ; i < size-2; i++)
{
for( j =1; j < size-1; j++)
{
for(k =2; k < size; k++){
if(a[i]!= a[j] && a[j] !=a[k] && a[k]!= a[i]){
sum = a[i] * a[j] * a[k];}
if(sum > large)
large = sum;
}
}
}
printf("\n%d\n", large);
#include<stdio.h>
int main()
{
int a[] = {1, 4, -10, 2, -3};
int sum =0, large=0;
int size = sizeof(a)/4;
int i =0, j=0, k =0;
if(size < 3)
return 0;
else if(size == 3)
return (a[0] * a[1] * a[2]);
for( i = 0 ; i < size-2; i++)
{
for( j =1; j < size-1; j++)
{
for(k =2; k < size; k++){
if(a[i]!= a[j] && a[j] !=a[k] && a[k]!= a[i]){
sum = a[i] * a[j] * a[k];}
if(sum > large)
large = sum;
}
}
}
printf("\n%d\n", large);
Find 3 highest numbers (magnitude wise)
case1: all positive
case 2: 1 positive 2 negative
case3 : all negative
case 1 and 2 will give you the answer
incase of case 3 we will have to find the highest postive number from the left over array . replace it with the smallest magnitude wise negative number. And then product them to get the answer
Having 5 variables to hold greatest positive int, 2 subsequent positive int and 2 greatest negative int.
populating all in one pass. If there is no positive int or no positive sum,printing 0.
time O(n), space constant
package com.project.euler;
public class MaxProduct {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {0, -1, 3, 100, -70, -5};//{1, 3, 5, 2, 8, 0, -1, 3};
int greatestPositiveInt = 0,maxPos1 = 0,maxPos2 = 0, maxNeg1 = 0, maxNeg2 = 0;
for(int i : a){
if(i>0){
if(greatestPositiveInt<i){
if(greatestPositiveInt!=0)
maxPos1 = greatestPositiveInt;
greatestPositiveInt = i;
}else{
if(maxPos1<i){
if(maxPos1!=0)
maxPos2 = maxPos1;
maxPos1 = i;
}else{
if(maxPos2<i){
maxPos2 = i;
}
}
}
}else{
if(i<0){
if(maxNeg1>i){
if(maxNeg1!=0)
maxNeg2 = maxNeg1;
maxNeg1 = i;
}else{
if(maxNeg2>i){
maxNeg2 = i;
}
}
}
}
}
if(maxPos1*maxPos2 > maxNeg1*maxNeg2)
System.out.println(maxPos1*maxPos2*greatestPositiveInt);
else{
System.out.println(maxNeg1*maxNeg2*greatestPositiveInt);
}
}
}
import java.util.LinkedList;
import java.util.List;
public class TestProgram {
static final int[] INPUT_ARRAY = { 1, 3, 5, 2, 8, 0, -1, 3 };
static long result = 1;
public static void main(String[] args) {
createCombinations(INPUT_ARRAY, 0, new LinkedList<Integer>(), 3);
System.out.println(result);
}
private static void createCombinations(int[] arrays, int idx, List<Integer> elements, int length) {
if (length == elements.size()) {
long temp = 1;
for (int i = 0; i < elements.size(); i++) {
temp *= elements.get(i);
}
if (temp > result)
result = temp;
return;
}
for (int i = idx; i < arrays.length; i++) {
elements.add(arrays[i]);
int temp = arrays[idx];
arrays[idx] = arrays[i];
arrays[i] = temp;
createCombinations(arrays, idx + 1, elements, length);
temp = arrays[i];
arrays[i] = arrays[idx];
arrays[idx] = temp;
elements.remove(elements.size() - 1);
}
}
}
int highestPositiveProduct(int* array, int size){
int largestPositive[3] = {0, 0, 0};
int largestNegative[2] = {0, 0};
int* ptr = NULL;
int largestPositiveNumber = 0;
int largestProduct = 0;
if (NULL == array || 0 >= size)
return 0;
ptr = array;
while (size > (ptr - array)){
if (0 < *ptr){
for (int index = 0; index < 3; ++index){
if (*ptr > largestPositive[index]){
largestPositive[index] = *ptr;
break;
}
}
}
else{
for (int index = 0; index < 2; ++index){
if (*ptr < largestNegative[index]){
largestNegative[index] = *ptr;
break;
}
}
}
}
largestPositiveNumber = largestPositive[0];
for (int index = 0; index < 3; ++index){
if (largestPositiveNumber < largestPositive[index]){
largestPositiveNumber = largestPositive[index];
}
}
largestProduct = largestPositive[0] * largestPositive[1] * largestPositive[2];
if (largestProduct < largestNegative[0] * largestNegative[1] * largestPositiveNumber){
largestProduct = largestNegative[0] * largestNegative[1] * largestPositiveNumber;
}
return largestProduct;
}
static int findLargestWithTop3() {
int[] num = {1, 3, 5, 2, 8, 0, -1, 3};
int maxpos1 = 0;
int maxpos2 = 0;
int maxpos3 = 0;
int maxneg1 = 0;
int maxneg2 = 0;
for(int i = 0; i<num.length; i++) {
if(num[i] > 0){
if(num[i] > maxpos1) {maxpos1 = num[i];}
} else {
if(num[i] < maxneg1) {maxneg1 = num[i];}
}
}
for(int i = 0; i<num.length; i++) {
if(num[i] > 0){
if(num[i] > maxpos2 && num[i] != maxpos1) {maxpos2 = num[i];}
} else {
if(num[i] < maxneg2 && num[i] != maxneg1) {maxneg2 = num[i];}
}
}
for(int i = 0; i<num.length; i++) {
if(num[i] > 0){
if(num[i] > maxpos3 && num[i] != maxpos1 && num[i] != maxpos2) {maxpos3 = num[i];}
}
}
int choice1, choice2;
choice1 = maxpos1*maxpos2*maxpos3;
choice2 = maxpos1*maxneg1*maxneg2;
if(choice1 > choice2) {
return choice1;
} else {
return choice2;
}
//System.out.println(maxpos1 + " " + maxpos2 + " " + maxpos3 + " " + maxneg1 + " " + maxneg2);
}
Most simplest but not efficient answer would be :
a = [7,3,5,-1,5,-11,5]
mul =0
for i in range(len(a)):
for j in range(i+1,len(a)):
if i==0:
mul = [a[i]*a[j],i,j]
if mul[0] < a[i]*a[j]:
mul = [a[i]*a[j],i,j]
print mul
mulF = mul
for i in range(len(a)):
if i not in (mul[1],mul[2]):
if mulF[0]<a[i]*mul[0]:
mulF = [a[i]*mul[0],i,mul[1],mul[2]]
print mulF
How about this. Add the items into 2 heaps, one for the positive and other for the negative numbers. both heaps will maintain the top high elements on it. then check if there are 2 negative numbers within the higher 3 possible integers to multiply, if not then select the 3 from the positive heap. that should take o(n) time for putting them into the separate heaps, and o(log n) to get them. so total o(n) complexity.
My approach:
1. First find the first 2 highest numbers based on magnitude (ignore the sign)
Ex:1st array: 8, 5
2nd array: 100, -70
2. Multiply these 2 highest numbers and get the result.
If the result is positive, you look for the next positive higher number
If the result is negative, you look for the next negative lower number
ex:1st array: 8*5 = 40, so, look for next higher positive number is 3 => 40x3=120
2nd array: 100* (-70) = -7000, look for next lower negative number is -5 => -7000x-5=35000
3. Always ignore 0 in our search because anything multiply by 0 is 0 => not good
Follow the approach I have 3 methods in java to support my method.
Overall this is O(n)
public int getMaxOf3(int[] array){
int prod = 1;
int highest_number_index=-1;
for (int i = 0; i < 2; i++) {
highest_number_index=findMaxMagnitude(array);
prod *= array[highest_number_index]; //first highest number * 2nd highest number
array[highest_number_index] = 0; //reset this number
}
if (prod > 0){
prod *= findMax(array);
}else{
prod *= findMin(array);
}
return prod;
}
public int findMaxMagnitude(int[] array){
int max_Index=0;
for (int i = 1; i < array.length; i++) {
if (Math.abs(array[max_Index]) < Math.abs(array[i])){
max_Index = i;
}
}
System.out.println("Max number: "+array[max_Index]);
return max_Index;
}
public int findMax(int[] array){
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (max <array[i])
max = array[i];
}
return max;
}
public int findMin(int[] array){
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (min >array[i])
min = array[i];
}
return min;
}
public static long product(int a[], int n)
{
int negCount = 0;
int max1, max2, max3;
max1=max2=max3 = Integer.MIN_VALUE;
int neg1,neg2;
neg1=neg2=Integer.MIN_VALUE;
long maxProduct = Long.MIN_VALUE;
for (int i = 0; i <n; i++) {
//we will get 3 Max possitive integer
if (max1 <a[i]) {
max3 = max2;
max2 = max1;
max1 = a[i];
} else if (max2 <a[i]) {
max3 = max2;
max2 = a[i];
} else if (max3 < a[i]) {
max3 = a[i];
}
// For 2 maxNegative Number (by |a[i]| Math.abs)
if (a[i] < 0) {
negCount++;
if (neg1 <Math.abs(a[i])) {
neg2 = neg1;
neg1 = a[i];
} else if (max2 <Math.abs(a[i])) {
neg2 = a[i];
}
}
}
if (negCount == 2) {
if (max1*neg1*neg2 > max1*max2*max3) {
maxProduct= max1*neg1*neg2 ;
}
} else {
maxProduct = max1*max2*max3;
}
System.out.println(max1+" "+ max2+" "+max3+" "+neg1+" "+neg2);
return maxProduct;
}
public static long product(int a[], int n)
{
int negCount = 0;
int max1, max2, max3;
max1=max2=max3 = Integer.MIN_VALUE;
int neg1,neg2;
neg1=neg2=Integer.MIN_VALUE;
long maxProduct = Long.MIN_VALUE;
for (int i = 0; i <n; i++) {
//we will get 3 Max possitive integer
if (max1 <a[i]) {
max3 = max2;
max2 = max1;
max1 = a[i];
} else if (max2 <a[i]) {
max3 = max2;
max2 = a[i];
} else if (max3 < a[i]) {
max3 = a[i];
}
// For 2 maxNegative Number (by |a[i]| Math.abs)
if (a[i] < 0) {
negCount++;
if (neg1 <Math.abs(a[i])) {
neg2 = neg1;
neg1 = a[i];
} else if (max2 <Math.abs(a[i])) {
neg2 = a[i];
}
}
}
if (max1*neg1*neg2 > max1*max2*max3) {
maxProduct= max1*neg1*neg2 ;
} else {
maxProduct = max1*max2*max3;
}
//System.out.println(max1+" "+ max2+" "+max3+" "+neg1+" "+neg2);
return maxProduct;
}
python 3 code:
from heapq import heappush, nlargest, heappop
def max_product(li):
myList = li[:]
negList = []
posList = []
[heappush(posList,x ) if x > 0 else heappush(negList,abs(x)) for x in [ x for x in myList if x != 0]]
if len(posList) > 3:
posLargest = nlargest(3,posList)
else:
posLargest = nlargest(len(posList), posList)
if len(negList) > 2:
negLargest = nlargest(2,negList)
else:
negLargest = nlargest(len(negList), negList)
if len(posList) < 1:
if len(negList) <= 1:
return "None"
if len(negList) > 1:
return negList[0] * negList[1]
if len(posList) == 1:
if len(negList) == 1:
return posList[0] * 1
else:
return posList[0] * negList[0] * negList[1]
if len(posList) > 1:
if len(negList) == 1:
endList = sorted(posList)
else:
endList = sorted(posList + negList)
if len(endList) >= 3:
max_prod = endList[-1] * endList[-2] * endList[-3]
elif len(endList) == 2:
max_prod = endList[-1] * endList[-2]
else:
max_prod = endList[0]
return max_prod
print(max_product([0,-1,3,100,-70,-50]))
My progam. Please check it.
public class ThreeMax {
/**
* @param args the command line arguments
*/
static int[] A = {1,3,5,-6,-9};
static int N = 5;
public static void main(String[] args) {
// TODO code application logic here
int a = A[0];
int b = A[1];
int c = A[2];
swap_three(0, 1, 2);
for(int i = 3; i < N ; i++){
if(Math.abs(A[i]) > c){
swap(i, 2);
swap_three(0, 1, 2);
}
}
int max = 1;
for(int i = 0; i<3; i++){
max *= A[i];
}
System.out.println(max);
}
static void swap_three(int a,int b, int c){
if(Math.abs(A[a]) < Math.abs(A[b])){
swap(a, b);
}
if(Math.abs(A[a]) < Math.abs(A[c])){
swap(a, c);
}
if(Math.abs(A[b]) < Math.abs(A[c])){
swap(b, c);
}
}
static void swap(int a,int b){
int tempt = A[a];
A[a] = A[b];
A[b] = tempt;
}
}
/**
*
*/
package Amazon;
/**
* @author mangesh
*
*/
public class MaxProduct {
/**
* @param args
*/
static int max1 = 0;
static int max2 = 0;
static int max3 = 0;
static int negativecnt = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {0, -1, 3, 100, -70, -5 };
for (int i = 0; i < a.length; i++) {
if (Math.abs(max1) < Math.abs(a[i])) {
if (a[i] < 0)
negativecnt++;
else
negativecnt = negativecnt > 0 ? negativecnt - 1 : 0;
max2 = max1;
max1 = a[i];
}
if (Math.abs(a[i]) < Math.abs(max1)) {
if (Math.abs(max2) < Math.abs(a[i])) {
max3 = max2;
if (a[i] < 0)
negativecnt++;
else
negativecnt = negativecnt > 0 ? negativecnt - 1 : 0;
max2 = a[i];
}
if (Math.abs(a[i]) < Math.abs(max2)) {
if (Math.abs(max3) < Math.abs(a[i])) {
if (a[i] < 0)
negativecnt++;
else
negativecnt = negativecnt > 0 ? negativecnt - 1 : 0;
max3 = a[i];
}
}
}
}
System.out.println(negativecnt+"Two no are:" + max1 + "," + max2 + "," + max3
+ "\n Product:" + max1 * max2 * max3);
if (negativecnt == 3) {
int max = findMax(a);
max3 = max;
} else if (negativecnt == 1) {
int max;
if (max1 < 0)
max = findMax(a);
else if (max2 < 0)
max = findMax(a);
else
max = findMax(a);
}
System.out.println("Two no are:" + max1 + "," + max2 + "," + max3
+ "\n Product:" + max1 * max2 * max3);
}
static int findMax(int a[]) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
return max;
}
int[] FindHighestTwo() {
int[] b = new int[2];
return b;
}
}
/**
*
*/
package Amazon;
/**
* @author mangesh
*
*/
public class MaxProduct {
/**
* @param args
*/
static int max1 = 0;
static int max2 = 0;
static int max3 = 0;
static int negativecnt = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = { 0, 1, 3, 100, -70, 5 };
for (int i = 0; i < a.length; i++) {
if (Math.abs(max1) < Math.abs(a[i])) {
max2 = max1;
max1 = a[i];
}
if (Math.abs(a[i]) < Math.abs(max1)) {
if (Math.abs(max2) < Math.abs(a[i])) {
max3 = max2;
max2 = a[i];
}
if (Math.abs(a[i]) < Math.abs(max2)) {
if (Math.abs(max3) < Math.abs(a[i])) {
max3 = a[i];
}
}
}
}
negativecnt = 0;
if (max1 < 0)
negativecnt++;
if (max2 < 0)
negativecnt++;
if (max3 < 0)
negativecnt++;
// System.out.println(negativecnt+"Two no are:" + max1 + "," + max2 +
// "," + max3+ "\n Product:" + max1 * max2 * max3);
if (negativecnt == 3) {
int max = findMax(a, 0, 0);
max3 = max;
} else if (negativecnt == 1) {
int max;
if (max1 < 0) {
max = findMax(a, max2, max3);
max1 = max;
} else if (max2 < 0) {
max = findMax(a, max1, max3);
max2 = max;
} else {
max = findMax(a, max1, max2);
max3 = max;
}
}
System.out.println("Two no are:" + max1 + "," + max2 + "," + max3
+ "\n Product:" + max1 * max2 * max3);
}
static int findMax(int a[], int exclude1, int exclude2) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
if (a[i] > max && a[i] != exclude1 && a[i] != exclude2)
max = a[i];
}
return max;
}
int[] FindHighestTwo() {
int[] b = new int[2];
return b;
}
}
public static int maxProduct(int[] in) {
int n1 = 0, n2 = 0, n3 = 0, n4 = 0, n5 = 0;
for (int e : in) {
if (e > n1)
n1 = e;
}
for (int e : in) {
if (e < n1 && e > n2)
n2 = e;
}
for (int e : in) {
if (e < n1 && e < n2 && e > n3)
n3 = e;
}
for (int e : in) {
if (e < n4)
n4 = e;
}
for (int e : in) {
if (e > n4 && e < n5)
n5 = e;
}
if (n2 * n3 > n4 * n5)
return n1 * n2 * n3;
return n1 * n4 * n5;
}
public static int highestProduct(int[] numbers) {
// find biggest positive number
// find two lowest negative numbers
// find the second and third biggest positive numbers
int posHigh = 0;
int posSec = 0;
int posThi = 0;
int negLow = 0;
int negSec = 0;
for (int i = 0; i < numbers.length; i++) {
int val = numbers[i];
if (val > posHigh) {
posThi = posSec;
posSec = posHigh;
posHigh = val;
} else if (val < posHigh && val > posSec) {
posThi = posSec;
posSec = val;
} else if (val < posSec && val > posThi) {
posThi = val;
}
if (val < negLow) {
negSec = negLow;
negLow = val;
} else if (val > negLow && val < negSec) {
negSec = val;
}
}
int ret1 = posHigh * posSec * posThi;
int ret2 = posHigh * negLow * negSec;
return (ret1 > ret2) ? ret1 : ret2;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MaxProduct
{
public class ProductResult
{
public int a { get; set; }
public int b { get; set; }
public int c { get; set; }
public long product
{
get
{
return a * b * c;
}
set{}
}
}
class Program
{
private static int length = 0;
private static List<int> Numbers;
private static List<ProductResult> Prods;
private static ProductResult Prod;
static void Main(string[] args)
{
while (true)
{
Numbers = new List<int>();
Prods = new List<ProductResult>();
System.Console.WriteLine("How many numbers would you like to enter ?");
length = int.Parse(System.Console.ReadLine().ToString());
System.Console.WriteLine("Enter the numbers : ");
for (int n = 0; n < length; n++)
{
Numbers.Add(int.Parse(System.Console.ReadLine().ToString()));
}
for (int m = 0; m < length; m++)
{
for (int n = 0; n < length; n++)
{
if (n == m) continue;
for (int o = 0; o < length; o++)
{
if (o == n || o == m) continue;
Prod = new ProductResult();
Prod.a = Numbers[m];
Prod.b = Numbers[n];
Prod.c = Numbers[o];
Prods.Add(Prod);
}
}
}
System.Console.WriteLine("The Maximum Product is : " + Prods.OrderByDescending(m => m.product).FirstOrDefault().product.ToString());
Console.ReadLine();
Console.Clear();
}
}
}
}
class HighestPossibleProductSolution {
public static Object highestProductOfThree(int[] arr) {
if (arr.length < 3) {
return null;
} else if (arr.length == 3) {
return (arr[0] * arr[1] * arr[2]);
}
int x;
int y;
int z;
if (arr[0] >= arr[1] && arr[0] >= arr[2]) {
x = arr[0];
if (arr[1] > arr[2]) {
y = arr[1];
z = arr[2];
} else {
y = arr[2];
z = arr[1];
}
} else if (arr[1] >= arr[0] && arr[1] >= arr[2]) {
x = arr[1];
if (arr[0] > arr[2]) {
y = arr[0];
z = arr[2];
} else {
y = arr[2];
z = arr[0];
}
} else {
x = arr[2];
if (arr[0] > arr[1]) {
y = arr[0];
z = arr[1];
} else {
y = arr[1];
z = arr[0];
}
}
for (int i = 3; i < arr.length; i++) {
if (arr[i] >= x) {
z = y;
y = x;
x = arr[i];
} else {
if (arr[i] >= y) {
z = y;
y = arr[i];
} else if (arr[i] > z) {
z = arr[i];
}
}
}
int min1;
int min2;
if (arr[0] > arr[1]) {
min1 = arr[1];
min2 = arr[0];
} else {
min2 = arr[1];
min1 = arr[0];
}
for (int i = 2; i < arr.length; i++) {
if (arr[i] <= min1) {
min2 = min1;
min1 = arr[i];
} else if (arr[i] < min2) {
min2 = arr[i];
}
}
System.out.println("MAX1: " + x + "\t MAX2: " + y + "\t MAX3: " + z + "\t MIN1: "
+ min1 + "\t MIN2: " + min2);
if ((x * min1 * min2) > (x * y * z)) {
return (x * min1 * min2);
}
return (x * y * z);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
}
public static void main(String[] args)
// TODO Auto-generated method stub
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
Integer x[]={1,3,5,2,8,0,10,-3};
TreeSet<Integer> y = new TreeSet<Integer>();
Collections.addAll(y, x);
Integer a[] = Arrays.asList(y.descendingSet().toArray()).toArray(new Integer[0]);
if((a[0] * a[1] * a[2]) > (a[0] * a[a.length -1] * a[a.length-2]))
System.out.println(a[0] * a[1] * a[2]);
else
System.out.println(a[0] * a[a.length -1] * a[a.length-2]);
//Find the first three maximum and first two minimum values and then return the Max of (three maxs and firstmax and first two mins)
public static int findHighestPositiveProduct(int[] a)
{
int max1=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int max3=Integer.MIN_VALUE;
int min1=Integer.MAX_VALUE;
int min2=Integer.MAX_VALUE;
for(int i=0;i<a.length;i++)
{
if(a[i]>max1)
{
max3=max2;
max2=max1;
max1=a[i];
}
else if(a[i]>max2)
{
max3=max2;
max2=a[i];
}
else
{
max3=a[i];
}
if(a[i]<min1)
{
min2=min1;
min1=a[i];
}
else if(a[i]<min2)
{
min2=a[i];
}
}
return Math.max((max1*max2*max3), (min1*min2*max1));
}
class Solution {
public int maxProduct(int[] nums) {
int prev_max = nums[0];
int prev_min = nums[0];
int currentMax = nums[0];
int currentMin=nums[0];
int result = nums[0];
for(int i = 1;i<nums.length;i++)
{
//max
currentMax = Math.max(Math.max(prev_min*nums[i],prev_max*nums[i]), nums[i]);
//min it will help if we have negative product and next value is negative like -2 3 -2
currentMin = Math.min(Math.min(prev_min*nums[i],prev_max*nums[i]), nums[i]);
result = Math.max(Math.max(currentMax,currentMin),result);
prev_max = currentMax;
prev_min=currentMin;
}
return result;
}
}
1) Find top 3 and bottom 2 values from the list in O(n)
- kr.neerav July 02, 20142) Let the list be [a, b, c ..... d, e]
3) The max among the following products will be the answer
abc
ade
abe
This takes into account the combination of negative numbers and all negative numbers also.