Amazon Interview Question for Quality Assurance Engineers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

- 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:

public static void runSolution() {
		int[] a = {-1, 2, 3, -4, -5, -2, -8, -4};
		
		System.out.println(findMaxProduct(a));
	}
	
	public static int findMaxProduct(int[] a) {
		if (a == null || a.length < 3) {
			return -1; // error
		}
				
		int nPos = 0; // count of positive nums.
		int nNeg = 0; // count of negative nums.
		int mPos1 = 0, mPos2 = 0, mPos3 = 0; // max. Found highest 3 positive
		int mNeg1 = 0, mNeg2 = 0, mNeg3 = 0; // max. Found lowest 3 negative 
		int mN1 = Integer.MIN_VALUE, mN2 = Integer.MIN_VALUE, mN3 = Integer.MIN_VALUE; // max. Found highest 3 negative 
		int zCount = 0; // count of zeros;
		
		for (int i = 0; i < a.length; i++) {			
			if (a[i] > 0) {
				nPos++;				
				if (a[i] > mPos1) {
					mPos3 = mPos2; mPos2 = mPos1; mPos1 = a[i];
				} else if (a[i] > mPos2) {
					mPos3 = mPos2; mPos2 = a[i];
				} else if (a[i] > mPos3) {
					mPos3 = a[i];
				}
			} else if (a[i] < 0) {  
				nNeg++;
				if (a[i] < mNeg1) {
					mNeg3 = mNeg2; mNeg2 = mNeg1; mNeg1 = a[i];
				} else if (a[i] < mNeg2) {
					mNeg3 = mNeg2; mNeg2 = a[i];
				} else if (a[i] < mNeg3) {
					mNeg3 = a[i];
				}				

				// store min negative if any
				if (a[i] > mN1) {
					mN3 = mN2; mN2 = mN1; mN1 = a[i];
				} else if (a[i] > mN2) {
					mN3 = mN2; mN2 = a[i];
				} else if (a[i] > mN3) {
					mN3 = a[i];
				}				
				
			} else {
				zCount++;
			}			
		}

		// fetch highest 3 * positive numbers
		int maxPos = 0;
		if (nPos >= 3) {
			maxPos = mPos1 * mPos2 * mPos3;
		}
		
		// fetch highest 1 positive * 2 negative		
		int maxPos2Neg = 0;
		if (nPos >= 1 && nNeg >= 2) {
			maxPos2Neg = mNeg1 * mNeg2 * mPos1;
		}

		// compare both if any and return highest
		if (maxPos > 0 && maxPos2Neg > 0) {
			return Math.max(maxPos, maxPos2Neg);
		} else if (maxPos > 0 && maxPos2Neg == 0) {
			return maxPos;
		} else if (maxPos == 0 && maxPos2Neg > 0) {
			return maxPos2Neg;
		}
				
		// return 0 if any found
		if (zCount > 1) {
			return 0;
		}
		
		// if all negative return 3 Min. negative
		if (nNeg >= 3) {
			return mN1*mN2*mN3;
		}
		
		return -1; // error should return any of the cases above.
	}

- guilhebl May 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous May 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just sort the array and then take product of first three elements and product of last three elements, return which ever one is greater.

- Anonymous May 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
            }
        }

- Anonymous May 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }

- Henry May 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

- MrWayne May 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Johnie May 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}

- Sridhar Jayapaul May 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

	}
}

- undefined May 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

	}

}

- harikrishna553 May 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

`Sort the array in ascending order and print the product of last three elements.
If you sort in descending order, them print the product of first three elements.

- Sathish Kumar June 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array and print the product of last three elements.

- Sathish Kumar June 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- Sri June 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- Sumit Burnwal November 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Asha December 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Asha December 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- maxasha December 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code:
n=[5,7,-8,-9,-6,2,10,11]
n.sort()
l=len(n)
print n
maxp=n[l-1]*n[l-2]*n[l-3]
if n[0]<0 and n[1]<0:
temp=n[0]*n[1]*n[l-1]
if temp>maxp:
maxp=temp
print maxp

- Shweta July 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

- GK May 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Wake up kids! What's the complexity for your solutions? Do they even work correctly?

Sort the array => O(n log(n))
Return mult of last 3 elements => O(1)

- Nix May 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Arrays.Sort(arr);

now take the last 3 elements in array
int n=arr.length-1;
maxproduct*=arr[n]*arr[n-1]*arr[n-2]

- Bhanu May 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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));

}

- sridharjayapaul May 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

First sort the array and then iterate to get the last 3 elements and multiply it.

- Rajeev May 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- anand May 30, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More