## Amazon Interview Question for Quality Assurance Engineers

• 0

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

}

}``````

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)

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]

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

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

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}``````

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

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

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

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

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!
if (leftMax <= current)
leftMax = current;

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

return null;
}``````

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;

}

}``````

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

}

}``````

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

}``````

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)
{
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");
}``````

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)
{
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");
}``````

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

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)
{
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");
}``````

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)
{
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");
}``````

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)
{
currentMax = num;
}
else if(num < currentMax)
{
possibleSolutions.Remove(I=>I > num);
}
}

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)
{
currentMax = num;
}
else if(num < currentMax)
{
possibleSolutions.Remove(I=>I > num);
}
}

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

foreach (var num in input)
{
if (num > currentMax)
{
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");
}

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

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]

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

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'

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

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)

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

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

``````public static void main(String[] args) {
int[] a = {1,2,5,9,6,8};
boolean blnFlagLess = true;
boolean blnFlagGreat = true;
for(int i=1; i<a.length; i++) {
for(int j=0; j<i; j++) {
if(a[i]<a[j]) {
blnFlagLess = false;
}
}

for(int k=i+1; k<a.length; k++) {
if(a[i]>a[k]) {
blnFlagGreat = false;
}
}
if(blnFlagLess && blnFlagGreat) {
System.out.println(a[i]);
blnFlagLess = true;
blnFlagGreat = true;
}
}
}``````

Here output will be 2 & 5.

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

``````public class SortCollectionHalf {

public static void main(String[] args) {
// TODO Auto-generated method stub

int a [] = {-2,4,-3,6,-1,5,8,9 };
int x= -2;

int i = 0;
int j = a.length - 1;

while (i < j) {
if (a[i] < x) {
i++;
}

if (a[j] > x) {
j--;
}

if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

for (int k = 0; k < a.length; k++) {
// System.out.println(" array after sorted");
System.out.print(" " + a[k]);
}

}``````

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

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.

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