Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
num = [1,-1,-2,4,-5]
# test case tested num = [1,3,2,0,-1,-5,-7,8,9,2,-3,-9,-12,15,-13]
##num = [-1,-2,-3,2,5]
#num.sort() [sort the given list of number]
#or use the below code
for i in range(1,len(num)):
for j in range(len(num)-1):
if num[j] > num[j+1]:
#num[j+1], num[j] = num[j], num[j+1]
t = num[j+1]
num[j+1] = num[j]
num[j] = t
#find the length of the list
#After sorting , fetch the first two and last two number and third last(in case) to avoid being -ve integer
le = len(num)
val1 = num[0]
val2 = num[1]
val3 = num[le-1]
val4 = num[le -2]
val_t = num[le-3]
val_ti = num[2]
#find the product of firts two(incase both are negative) and last two numbers
val_new = val1*val2
val_new2 = val3*val4
if val_new2 < val_new:
val_prod = val_new
val_max_prod = val_prod * val3 # if first two are negative and product is more than last two multiply the product with last number
print val_max_prod
else:
val_prod = val_new
if val_new*val_t > val_prod*val_ti: #incase -5,-4,-3,4,6
print val_new*val_t
else:
print val_prod*val_ti
static void MaxProduct(int[] arr2)
{
List<int> list = arr2.ToList();
list = list.OrderBy(x => x).ToList();
Tuple<int, int, int> tuple;
var s1 = list[0];
var s2 = list[1];
var s3 = list[2];
var e1 = list[list.Count - 1];
var e2 = list[list.Count - 2];
var e3 = list[list.Count - 3];
var sProdduct = s1 * s2 * s3;
var eProdduct = e1 * e2 * e3;
if (sProdduct > 0 && sProdduct >= eProdduct)
{
tuple = new Tuple<int, int, int>
(
item1: list[0],
item2: list[1],
item3: list[2]
);
}
else if (sProdduct < 0 && -sProdduct >= eProdduct)
{
if (s3 < 0)
{
tuple = new Tuple<int, int, int>
(
item1: list[0],
item2: list[1],
item3: list[list.Count - 1]
);
}
else if (s2 < 0)
{
tuple = new Tuple<int, int, int>
(
item1: list[0],
item2: list[list.Count - 1],
item3: list[2]
);
}
else
{
tuple = new Tuple<int, int, int>
(
item1: list[list.Count - 1],
item2: list[1],
item3: list[2]
);
}
}
else
{
tuple = new Tuple<int, int, int>
(
item1: list[list.Count - 1],
item2: list[list.Count - 2],
item3: list[list.Count - 3]
);
}
Console.WriteLine("Output: {0}, {1}, {2} and Maximu Product: {3}",
tuple.Item1, tuple.Item2, tuple.Item3,
tuple.Item1 * tuple.Item2 * tuple.Item3);
}
}
static void MaxProduct(int[] arr2)
{
List<int> list = arr2.ToList();
list = list.OrderBy(x => x).ToList();
Tuple<int, int, int> tuple;
// First three numbers in the beginning of the sorted list
var s1 = list[0];
var s2 = list[1];
var s3 = list[2];
// Last three numbers in the sorted list end
var e1 = list[list.Count - 1];
var e2 = list[list.Count - 2];
var e3 = list[list.Count - 3];
var sProdduct = s1 * s2 * s3;
var eProdduct = e1 * e2 * e3;
if (sProdduct > 0 && sProdduct >= eProdduct)
{
tuple = new Tuple<int, int, int>
(
item1: s1,
item2: s2,
item3: s3
);
}
else if (sProdduct < 0 && -sProdduct >= eProdduct)
{
if (s3 < 0)
{
tuple = new Tuple<int, int, int>
(
item1: s1,
item2: s2,
item3: e1
);
}
else if (s2 < 0)
{
tuple = new Tuple<int, int, int>
(
item1: s1,
item2: e1,
item3: s3
);
}
else
{
tuple = new Tuple<int, int, int>
(
item1: e1,
item2: s2,
item3: s3
);
}
}
else
{
tuple = new Tuple<int, int, int>
(
item1: e1,
item2: e2,
item3: e3
);
}
Console.WriteLine("Output: {0}, {1}, {2} and Maximu Product: {3}",
tuple.Item1, tuple.Item2, tuple.Item3,
tuple.Item1 * tuple.Item2 * tuple.Item3);
}
}
import java.util.Arrays;
import java.util.Random;
public class MaximumProduct {
public static void main(String[] args) {
// TODO Auto-generated method stub
Random random = new Random();
int[] array = new int[200];
for (int i = 0; i < 200; i++) {
array[i] = random.nextInt(10);
}
Arrays.sort(array);
int maxproduct = 1;
for (int j = array.length - 1; j >= array.length - 3; j--) {
maxproduct *= array[j];
}
System.out.println(maxproduct);
}
}
I feel like people are making the logic more complicated than it needs to be. If MAX1 is the number furthest to the right on the natural number line and MIN1 is the number furthest to the left then there are only two possible candidates for largest triplet:
Candidate 1: MAX1 * MAX2 * MAX3
Candidate 2: MAX1 * MIN1 * MIN2
This is true for all natural numbers. To optimize we can exclude candidate 2 if MAX1 <= 0.
Find these and compare, time: O(n), space O(1).
public static void maxThree(int[] a){
int max = Integer.MIN_VALUE;
int smax =Integer.MIN_VALUE;
int tmax = Integer.MIN_VALUE;
for (int i = 0; i <a.length-1 ; i++) {
if (a[i]>max){
tmax =smax;
smax=max;
max =a[i];
}else if (a[i]>smax){
tmax =smax;
smax=a[i];
}else if(a[i]>tmax){
tmax = a[i];
}
}
System.out.println(String.format("max value %s second max value %s and third max value %s", max,smax,tmax));
}
We need to consider following cases
what if array has only -ves.
what if array has only +ves.
what if array has 0.
Whats if array has both +ves and -ves
Sort array,
a. If array has more than 1 -ve values, take first 2 negatives and last positive compute product.
b. If array has only 1 -ve value (or) only positive values, compute product of last 3 numbers.
Compare the product with the product you computed in step 1. Return max product.
import java.util.Arrays;
import java.util.Objects;
public class ArrayUtil {
public static int maxProduct(int arr[]) {
if (Objects.isNull(arr)) {
throw new NullPointerException("Array shouldn't be null");
}
if (arr.length < 3) {
throw new IllegalArgumentException(
"Array should have atleast 3 elements");
}
Arrays.sort(arr);
int length = arr.length;
int maxProduct = Integer.MIN_VALUE;
if (arr[0] >= 0 || (arr[0] <= 0 && arr[1] >= 0)) {
maxProduct = arr[length - 1] * arr[length - 2] * arr[length - 3];
}
if (arr[0] < 0 && arr[1] < 0) {
int tmpProduct;
if (arr[length - 1] >= 0) {
tmpProduct = arr[0] * arr[1] * arr[length - 1];
} else {
tmpProduct = arr[length - 1] * arr[length - 2]
* arr[length - 3];
}
if (maxProduct < tmpProduct)
return tmpProduct;
}
return maxProduct;
}
}
We need to consider following cases
what if array has only -ves.
what if array has only +ves.
what if array has 0.
Whats if array has both +ves and -ves
Sort array,
a. If array has more than 1 -ve values, take first 2 negatives and last positive compute product.
b. If array has only 1 -ve value (or) only positive values, compute product of last 3 numbers.
Compare the product with the product you computed in step 1. Return max product.
import java.util.Arrays;
import java.util.Objects;
public class ArrayUtil {
public static int maxProduct(int arr[]) {
if (Objects.isNull(arr)) {
throw new NullPointerException("Array shouldn't be null");
}
if (arr.length < 3) {
throw new IllegalArgumentException(
"Array should have atleast 3 elements");
}
Arrays.sort(arr);
int length = arr.length;
int maxProduct = arr[length - 1] * arr[length - 2] * arr[length - 3];
if (arr[0] < 0 && arr[1] < 0) {
int tmpProduct;
if (arr[length - 1] >= 0) {
tmpProduct = arr[0] * arr[1] * arr[length - 1];
} else {
tmpProduct = arr[length - 1] * arr[length - 2]
* arr[length - 3];
}
if (maxProduct < tmpProduct)
return tmpProduct;
}
return maxProduct;
}
}
The logic that i am using is that get the top 3 maximum numbers and bottom 2 minimum numbers , and then find the maximum between the product of top two numbers and bottom two numbers (this takes care if the list has negative numbers and the product of negative numbers is positive ). Finally return the highest number with the max number we got in the previous step.
import heapq
def maximum_product(l):
top_three_maximum = heapq.nlargest(3,l)
bottom_two_minimum = heapq.nsmallest(2,l)
max_num = max((top_three[1]*top_three[2]),(bottom_two[0]*bottom_two[1]))
print top_three[0]*max_num
maximum_product([5, 6, 2, 8, 4, 1, 10, 12, 3, 15])
public class MaxMultiplesInAnArray {
public static void main(String[] args) {
int[] a= {-8,3,2,-6,7,-2,5,9,-7};
System.out.println("Max unique Multiples obtained is: "+(a.length*(a.length-1)/2));
List<Integer> al=new ArrayList<Integer>();
for (int i=0;i<a.length;i++) {
al.add(a[i]);
}
Collections.sort(al);
int s=al.size();
System.out.println(al);
int x=al.get(0)*al.get(1)*al.get(s-1);
int y=al.get(s-1)*al.get(s-2)*al.get(s-3);
int z= (x>y?x:y);
System.out.println("max product is: "+z);
}
}
public static void maxMult(){
int arr1[] = {-22,-2,-5,-21,-12,-7,-14};
int max1=arr1[0],max2 =arr1[1],max3 =arr1[2];
for(int i =3;i<arr1.length ; i++){
int first = arr1[i]; // 0: -20
if(first>max1){ //-20 >-2
max1= first; //0: max1= -20
}
if(max1>max2){ //0: -20>-2
if(max1<0){
}
int temp = max2; //temp = -2
max2=max1;
max1=temp;
}
if(max2>max3){
int temp = max3;
max3= max2;
max2=temp;
}
System.out.println("Itereation"+ i);
System.out.println("Max1 = "+ max1 + " and max2 ="+ max2+" and max3 ="+ max3);
}
System.out.println(max1*max2*max3);
}
public static void maxMult(){
int arr1[] = {-22,-2,-5,-21,-12,-7,-14};
int max1=arr1[0],max2 =arr1[1],max3 =arr1[2];
for(int i =3;i<arr1.length ; i++){
int first = arr1[i];
if(first>max1){
max1= first;
}
if(max1>max2){
int temp = max2;
max2=max1;
max1=temp;
}
if(max2>max3){
int temp = max3;
max3= max2;
max2=temp;
}
System.out.println("Itereation"+ i);
System.out.println("Max1 = "+ max1 + " and max2 ="+ max2+" and max3 ="+ max3);
}
System.out.println(max1*max2*max3);
}
public static void maxMult(){
int arr1[] = {-22,-2,-5,-21,-12,-7,-14};
int max1=arr1[0],max2 =arr1[1],max3 =arr1[2];
for(int i =3;i<arr1.length ; i++){
int first = arr1[i];
if(first>max1){
max1= first;
}
if(max1>max2){
int temp = max2;
max2=max1;
max1=temp;
}
if(max2>max3){
int temp = max3;
max3= max2;
max2=temp;
}
System.out.println("Itereation"+ i);
System.out.println("Max1 = "+ max1 + " and max2 ="+ max2+" and max3 ="+ max3);
}
System.out.println(max1*max2*max3);
}
public static void main(String[] args) {
int[] a= {-1,-2, 1,2,3,5,-9};
int maxProd =0, temp, i1=0, i2=0, i3=0;
for(int i=0; i<a.length; i++) {
for(int j=i+1; j<a.length; j++) {
for(int k=j+1; k<a.length; k++) {
temp = a[i] * a[j] * a[k];
if(temp>maxProd) {
maxProd = temp;
i1 = a[i];
i2 = a[j];
i3 = a[k];
}
}
}
}
System.out.println("Max product is " + maxProd + " with values: " + i1 + " * " + i2 + " * " + i3);
}
public static void maxThree(int[] a){
int max = Integer.MIN_VALUE;
int smax =Integer.MIN_VALUE;
int tmax = Integer.MIN_VALUE;
for (int i = 0; i <a.length-1 ; i++) {
if (a[i]>max){
tmax =smax;
smax=max;
max =a[i];
}else if (a[i]>smax){
tmax =smax;
smax=a[i];
}else if(a[i]>tmax){
tmax = a[i];
}
}
System.out.println(String.format("max value %s second max value %s and third max value %s", max,smax,tmax));
}
public class MaxProductOfThreeNumbers {
static int maxproduct(int[] array) {
if (array == null || array.length < 3) {
throw new IllegalArgumentException("Invalid argument");
}
Integer max1 = Integer.MIN_VALUE;
Integer max2 =Integer.MIN_VALUE;
Integer max3 = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
int comp = array[i];
if (comp > max1) {
max1 = comp;
}
if (max2 < max1) {
int tmp = max2;
max2 = max1;
max1 = tmp;
}
if (max2 > max3) {
int tmp = max2;
max2 = max3;
max3 = tmp;
}
}
System.out.println("Max values : " + max1 + ", " + max2 + ", " + max3);
return (max1.intValue() * max2.intValue() * max3.intValue());
}
public static void main(String[] args) {
int[] array = {5, 6, 2, 8, 4, 1, 10, 12, 3, 15};
System.out.println("Max product : "+ maxproduct(array));
}
}
OUTPUT:
-------------
Max values : 10, 12, 15
Max product : 1800
Complexity : O(n)
- Try to find Max of 3 positive numbers in array or else max of 2 neg, 1 pos. Return max of these 2.
- If not found try to find 1 zero, if any then return 0;
- if not then try to find 3 highest negative (closest to zero) return their product.
Time: O(n) - space O(1).
Algorithm implementation in Java:
- guilhebl May 06, 2016