Amazon Interview Question for Quality Assurance Engineers


Country: India
Interview Type: In-Person




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

Time Complexity: O(n) where n is the size of the input array. Space: O(n)
public class FindNumSvc {
	
	public static int findNum(int[] arr){
		if(arr == null || arr.length < 2){
			throw new IllegalArgumentException();
		}
		int[][] minMax = new int[2][arr.length];
		int max = arr[0];
		for(int i = 1; i < arr.length; i++){
			minMax[0][i] = max;
			max = Math.max(arr[i], max);
		}
		int min = arr[arr.length - 1];
		for(int i = arr.length - 2; i >= 0; i--){
			minMax[1][i] = min;
			min = Math.min(arr[i], min);
		}
		for(int i = 1; i < arr.length - 1; i ++){
			if(minMax[0][i] < arr[i] && minMax[1][i] > arr[i]){
				return i;
			}
		}
		if(minMax[0][arr.length - 1] < arr[arr.length - 1]){
			return arr.length - 1;
		}
		return minMax[1][0] > arr[0]? 0:-1;
	}

	public static void main(String[] args) {
		int[] arr = {-1,4,-3,6,-2,5,8,9};
		System.out.println(findNum(arr));

	}

}

- divm01986 January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

As per my understanding,
We have to find a number in array which is greater than all numbers lies on left side and lesser than all numbers lies on right side in the array.

e.g.
arr[] = 5,4,3,7,4,1,2,8,10

Output - 8 (all elements at left side are lesser than 8 and all elements at right side are greater than 8).

My solution-
I will create 2 arrays-
1- First array will hold max value in array before that index.(Traverse from left side to get the values), for above array , the array will be -
lmax = 5,5,5,5,7,7,7,7,8 (Take first element as it is in origin array)
2- Second array will hold min value in array after the index.(Traverse from right side to get the values), For above array, the second array will be -
rmin = 1,1,1,1,1,2,8,10,10 (Take last element as it is in origin array)

Now traverse the origin array and check condition-
if(arr[i] >= lmax[i] && arr[i] <= rmin[i]){
print(arr[i])
}

Space complexity O(2n) - Need to create min max array
Time complexity - O(n)

- azambhrgn January 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Time Complexity : O(n)

Algorithm:

Take arr as input array
Initialise 2 pointers
value_under_test to the index position "0"
Ptr1 to the index position "value_under_test + 1"

while (Ptr1 < max_array_size)
{

If (arr[Ptr1] > arr[value_under_test])
{
Keep advancing Ptr1 to next position
}
Else
{
advance value_under_test to position "Ptr1 + 1"
advance Ptr1 to position "value_under_test + 1"
}
}


//Once this while loop is completed, we know for sure that all values lying after position "value_under_test" is greater
//now all we have to do is to ensure that anything lying behind position "value_under_test" is smaller


loop from "value_under_test - 1" to 0
{
if any item is greater than value in position "value_under_test"
{
Inform user that no such number exist in this array
}
}

//if this loop runs fully, it means that the value at position "value_under_test" is the number that we are looking for!!!

So, return arr[value_under_test]

- SANTHOSH0605 February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Can be solved with quick sort pivot element logic.
Make given element as pivot.

Sorry , I didn't get the question properly. Check my other reply to understand question and provided solution.
Thanks

- azambhrgn January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not clear about the question. Could you please give an example?

- yankeson2013 January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My version of required function is:

/**
   *
   * @param a
   * @return position of the first element with property that all elements in previous positions
   *         are less than this element - from the left side, and all elements in positions
   *         that greater or equal goes after the element - from the right side
   */
  static int findMiddleElementPosition(int[] a) {
    if (a == null) {
      return -1;
    }
    int[] max = Arrays.copyOf(a, a.length);
    for (int i = 1; i < a.length; i++) {
      if (max[i] < max[i - 1]) {
        max[i] = max[i - 1];
      }
    }
    for (int j = a.length - 1; j >= 0; j--) {
      if (a[j] < max[j]) {
        // additional check if it is the latest element in the array
        return j + (j != a.length - 1 ? 1 : 0);
      }
    }
    return 0;
  }

Samples in format array:position

{null, -1},
        {new int[]{1}, 0},
        {new int[]{1, 2}, 0},
        {new int[]{1, 2, 3}, 0},
        {new int[]{2, 1, 3}, 2},
        {new int[]{-1, 2, -3, 4, 5, 6}, 3},
        {new int[]{-1, 4, -3, 6, -2, 5, 8, 9}, 6},
        {new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 0},
        {new int[]{-1, -2, -3, -4, -5, -6, -7, -8, -9}, 8},
        {new int[]{-1, -1, -1, -1, 3, 3, 3, 3}, 0},
        {new int[]{-1, 2, -1, 3, -1, 4, 4, 4, 4}, 5}

- Mike L January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

No It we can't reason it change the array structure...

- neelabhsingh January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a modified quick sort partition function:

function partition (index, A) {
	var i = 0
	var j = A.length - 1
	var partition = A[index]
	while (i <= j) {
		while (A[i] < partition) {
			i++
		}
		while (A[j] > partition) {
			--j
		}
		if (i <= j) {
			if (A[i] !== A[j]) {
				return false
			}
// Don't need all this...
//
//			var tmp = A[j]
//			A[j] = A[i]
//			A[i] = tmp
//			i++
//			j--
		}
	}
	return true
}

module.exports = function (sequence) {
	for (var i = 0; i < sequence.length; ++i) {
		if (partition(i, sequence)) {
			return sequence[i]
		}
	}
	return null
}

var sequence = [4, 3, 2, 7, 12, 11, 15, 22, 18, 9, 13]


var solution = module.exports(sequence)
console.log(solution)

- srterpe January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution. Tricky but fun problem!

#include <array>
#include <limits>
#include <iostream>

int main(void)
{
	std::array<int, 10> values {0, 1, 5, 3, 2, 8, 9, 9, 0, 11};

	int maxLeft = std::numeric_limits<int>::min();
	int maxIndex = 0;

	int minRight = std::numeric_limits<int>::max();
	int minIndex = 0;

	int leftIndex = 0;
	int rightIndex = values.size()-1;

	for(;;)
	{
		auto leftValue = values[leftIndex];
		auto rightValue = values[rightIndex];

		if(leftValue > maxLeft)
		{
			maxLeft = leftValue;
			maxIndex = leftIndex;
		}

		if(rightValue < minRight) 
		{
			minRight = rightValue;
			minIndex = rightIndex;
		}

		leftIndex++;
		rightIndex--;

		if(leftIndex >= rightIndex)
			break;
	}

	if(maxLeft < minRight)
	{
		std::cout << "#" << minRight << " at index " << minIndex << " is a match!" << std::endl;
	}
	else
	{
		std::cout << "no match!" << std::endl;
	}

	return 0;
}

- snichols@therealm.io January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int? FindFirstPartition(int[] arr)
        {
            if (arr == null)
                return null;
            if (arr.Length == 0)
                return arr[0]; // the single ellement is in fact a "partition"

            var minValues = new Stack<int>();

            for (var i = arr.Length - 1; i > 0; i--)
            {
                if (minValues.Count == 0)
                    minValues.Push(arr[i]);
                else
                {
                    var min = minValues.Peek();
                    if (arr[i] <= min)
                        minValues.Push(arr[i]);
                }
            }

            var leftMax = int.MinValue;

            foreach (var current in arr)
            {
                if (current >= leftMax && (minValues.Count == 0 || current <= minValues.Peek()))
                    return current; // found it!
                // Otherwise, advance!
                if (leftMax <= current)
                    leftMax = current;

                if (minValues.Peek() == current)
                    minValues.Pop();
            }

            return null;
        }

- aurelian.lica January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static  int TheNumberXBalance(ArrayList TheListToCheck )
{
  
    
     if (TheListToCheck==null && TheListToCheck.isEmpty())
         return -1;
     
    for(int k=0;k<TheListToCheck.size();k++)
    {
     
        if(partBalance(TheListToCheck,k,0,TheListToCheck.size()-1))
              System.out.println("Value:"+TheListToCheck.get(k)+" at index["+k+"]");
        
      }
     
  
  return 1;
}

public static boolean partBalance(ArrayList TheListToCheck,int index_pivot,int start,int end)
{
      
     int pivot=(int)TheListToCheck.get(index_pivot);
    int indexinitLeft= start;
    int indexendLeft=index_pivot-1;
    int indexinitRight= pivot+1;
    int  indexendRight=end;
    
        
      
      int leftval=(int)TheListToCheck.get(indexinitLeft);
      int rightval=(int)TheListToCheck.get(indexendRight);
      
      
        while(index_pivot>indexinitLeft)
      {
        
        leftval=(int)TheListToCheck.get(indexinitLeft);
         //System.out.println("Compare:"+pivot+" with:"+leftval);
        if(pivot<=leftval)
        {
            return false;
            
        }
        else {
            indexinitLeft++;
        
        }
      }   
        
      
        
        
         while(index_pivot<indexendRight)
      {
        
        rightval=(int)TheListToCheck.get(indexendRight);
        //System.out.println("Compare:"+pivot+" with r"+rightval);
        if(pivot>=rightval)
        {
            return false;
        
        }else
        {
         indexendRight--;   
            
        }
      }


 return true;

}
    
}

- prizkaboom January 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package careerCup;

import java.util.Arrays;

public class SortCollectionInHalf
{
	
	int sortData(int [ ] inp, int elm)
	{
		
		Arrays.sort( inp, 0, inp.length / 2 );
		Arrays.sort( inp, inp.length / 2, inp.length );
		System.out.println( Arrays.toString( inp ) );
		
		int mid = 0;
		int left = 0;
		int right = inp.length - 1;
		
		while ( right >= left )
		{
			
			mid = ( left + right ) / 2;
			
			if ( inp[ mid ] == elm )
			{
				
				System.out.println( "Element " + +inp[ mid ]
						+ " found at index: " + mid );
				return mid;
			}
			else if ( inp[ mid ] > elm )
			{
				
				right = mid - 1;
				
			}
			else if ( inp[ mid ] < elm )
			{
				
				left = mid + 1;
			}
			else
			{
				
				return -1;
			}
			
		}
		
		return mid;
		
	}
	
	public static void main(String [ ] args)
	{
		
		int [ ] inp = { -2, 4, -3, 6, -1, 5, 8, 9 };
		SortCollectionInHalf so = new SortCollectionInHalf( );
		so.sortData( inp, -2 );
		
	}
	
}

- Sandy0109 February 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity - O(n)

import java.util.Scanner;

public class two {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int size = scan.nextInt();
		int[] arr = new int[size];
		
		for(int i =0;i< size;i++){
			arr[i] = scan.nextInt();
		}
		scan.close();
		findIndex(arr, size);
	}
	
	private static void findIndex(int[] arr, int size){
		Integer pivot=null;
		int pivotIndex = 0;
		int max=Integer.MIN_VALUE;
		for(int i=0;i< size;i++){
			if(pivot==null)
			{
				if(max<arr[i])
				{
					max=arr[i];
					pivotIndex=i;
					pivot=arr[i];
				}
			}
			else{
				if(pivot.intValue()>arr[i])
				{
					pivot=null;
				}
				else{
					max=arr[i];
				}
			}
		}
		System.out.println(pivot==null?"No Element available" :pivotIndex);
	}

}

- ankur7026 February 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int currentMax = 0;
                HashSet<int> possibleSols = new HashSet<int>();

                foreach (var num in input)
                {
                    if (num > currentMax)
                    {
                        possibleSols.Add(num);
                        currentMax = num;
                    }
                    else if (num < currentMax)
                    {
                        possibleSols.RemoveWhere(i => i > num);
                    }
                }
                if(possibleSols.Count > 0)
                {
                    Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
                }
                else
                {
                    Console.WriteLine("No such element exists");
                }

- Murali K February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int currentMax = 0;
                HashSet<int> possibleSols = new HashSet<int>();

                foreach (var num in input)
                {
                    if (num > currentMax)
                    {
                        possibleSols.Add(num);
                        currentMax = num;
                    }
                    else if (num < currentMax)
                    {
                        possibleSols.RemoveWhere(i => i > num);
                    }
                }
                if(possibleSols.Count > 0)
                {
                    Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
                }
                else
                {
                    Console.WriteLine("No such element exists");
                }

- Murali K February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int currentMax = 0;
HashSet<int> possibleSols = new HashSet<int>();

foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}

- Murali K February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity: O(n)
Space Complexity: at max O(n) - case if the input is a sorted array.

This problem can have more than one solution.

int currentMax = 0;
                HashSet<int> possibleSols = new HashSet<int>();

                foreach (var num in input)
                {
                    if (num > currentMax)
                    {
                        possibleSols.Add(num);
                        currentMax = num;
                    }
                    else if (num < currentMax)
                    {
                        possibleSols.RemoveWhere(i => i > num);
                    }
                }
                if(possibleSols.Count > 0)
                {
                    Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
                }
                else
                {
                    Console.WriteLine("No such element exists");
                }

- Murali K February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity: O(n)
Space Complexity: at max O(n) - case if the input is a sorted array.

This problem can have more than one solution.

int currentMax = 0;
                HashSet<int> possibleSols = new HashSet<int>();

                foreach (var num in input)
                {
                    if (num > currentMax)
                    {
                        possibleSols.Add(num);
                        currentMax = num;
                    }
                    else if (num < currentMax)
                    {
                        possibleSols.RemoveWhere(i => i > num);
                    }
                }
                if(possibleSols.Count > 0)
                {
                    Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
                }
                else
                {
                    Console.WriteLine("No such element exists");
                }

- Murali K February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Notes: This problem may contain more than one solution.
Time complexity - O(n)
Space Complexity - O(n) - if the input is a sorted array, then every elements in the array could be a possible solution.


int currentMax = int.MinValue;
hashset<int> possibleSolutions = new Hashset<int>();

foreach(var num in input)
{
if(num > currentMax)
{
possibleSolutions.Add(num);
currentMax = num;
}
else if(num < currentMax)
{
possibleSolutions.Remove(I=>I > num);
}
}

- Murali K February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Notes: This problem may contain more than one solution.
Time complexity - O(n)
Space Complexity - O(n) - if the input is a sorted array, then every elements in the array could be a possible solution.


int currentMax = int.MinValue;
hashset<int> possibleSolutions = new Hashset<int>();

foreach(var num in input)
{
if(num > currentMax)
{
possibleSolutions.Add(num);
currentMax = num;
}
else if(num < currentMax)
{
possibleSolutions.Remove(I=>I > num);
}
}

- Anonymous February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}

- Murali K February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <algorithm>
#include <iostream>

using namespace std;
int main() {
  int A[] = {5, 4, 6, 10, 7, 8, 9, 11, 23, 40};
  int size = sizeof(A) / sizeof(A[0]);
  int B[100];
  for (int i = 0; i < size; i++) {
    B[i] = A[i];
  }
  sort(A, A + size);
  for (int i = 0; i < size; i++) {
    if (A[i] == B[i])
      cout << i << " " << A[i] << endl;
  }
  return -1;
}

- singh.chakresh March 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

PYTHON::

>>> def example(val, list):
a = []
b = []
for i in list:
if i < val:
a.append(i)
elif i > val:
b.append(i)
a.append(val)
a.extend(b)
return a

>>> example(2, [4,5,6,2,3,1,0])
[1, 0, 2, 4, 5, 6, 3]
>>> example(3, [4,5,6,2,3,1,0])
[2, 1, 0, 3, 4, 5, 6]

- Madhu Mohan May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution in C#:

int[] myArr = new int[] { -1, 2, -1, 3, -1, 4, 7, 8, 6 };
            int[] myArr1 = new int[myArr.Length];
            int iVal = 0;
            int iVal1 = 0;
            int iMA;
            for (iMA = 1; iMA < myArr.Length - 1; iMA++)
            {
                if (myArr[iMA] > myArr[iMA - 1] && myArr[iMA] < myArr[iMA + 1])
                {
                    iVal = 0;
                    iVal1 = 0;
                    for (int iMA1 = iMA; iMA1 < myArr.Length - 1; iMA1++)
                    {
                        if (myArr[iMA] < myArr[iMA1 + 1])
                        {
                            iVal++;
                        }
                    }
                    for (int iMA2 = iMA; iMA2 >= 0; iMA2--)
                    {
                        if (myArr[iMA] > myArr[iMA2])
                        {
                            iVal1++;
                        }
                    }
                }
                if ((iVal + iVal1) == (myArr.Length - 1))
                {                    
                    break;
                }
            }

            if ((iVal + iVal1) != (myArr.Length - 1))
            {
                iVal = 0;
                iVal1 = 0;
            }

            if (iVal1 == 0 && iVal == 0)
            {
                Console.WriteLine("No Such element");
            }
            else
            {
                Console.WriteLine("Element at position " + iMA + " has all digits less than it to the left anf all digits greater than it to the right");
            }

            Console.Read();

- Anonymous October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

l=[6,5,4,3,5,7,8,9]
max=l[0]
found=0
for i in range(1,len(l)-1):
if(l[i]>l[i-1] and l[i]>max):
max=l[i]
flag=0
for j in range(i+1,len(l)):
if(l[i]<l[j]):
continue
else:
flag=1
break
if(flag==0):
print l[i]
found=1
break
if(found==0):
print 'No such element found'

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

----Python code---

array1=[3,64,1,100,620,269,180]
arryLength=len(array1)
i=0
while i in range(arryLength-2):
    i=i+1 
    if array1[i]<array1[i+1] and array1[i]>array1[i-1]:
        print(array1[i])
    else:
       continue

- blankspace August 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

x = [10,3,4,5,6,8,2,1,11,12,8,6,13,17]
x.sort()

index = (int(len(x)/2))
print (x)
if x[index] <= x[index+1] and x[index] >= x[index-1]:
print ("This is number ",x[index], "and position is ",index)

- Anil February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

x = [10,3,4,5,6,8,2,1,11,12,8,6,13,17]
x.sort()

index = (int(len(x)/2))
print (x)
if x[index] <= x[index+1] and x[index] >= x[index-1]:
    print ("This is number ",x[index], "and position is ",index)

- Anil February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort the given array then print last but one.

Python program

array = [5,4,3,7,4,1,2,8,10]
array.sort();
print array[-2]

- Raghu February 04, 2017 | 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