## Amazon Interview Question for Quality Assurance Engineers

• 0

Team: AWS
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 12 vote

By assuming array elements are sorted in ascending order, below is the algorithm(which will take care of duplicate elements as well).

``````void All_Sum_Pair(int A[], int start, int end, int SUM)
{
int temp = 0;
if(start<end){
temp = A[start] + A[end];
if(temp == SUM){
print("(%d, %d), ",A[start], A[end]);
All_Sum_Pair(A, start+1, end, SUM);
All_Sum_Pair(A, start, end-1, SUM);
} else if(temp > SUM){
All_Sum_Pair(A, start, end-1, SUM);
} else {
All_Sum_Pair(A, start+1, end, SUM);
}
}
}``````

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

from where the variables 's' and 'e' are coming ?

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

This will definitely throw arrayindexoutofbound exception

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

I think by "pairs" he means just 2 nos. summing to the value of N.

Store the values in a HashMap. Iterate over each value "x" in the array and find N-x in the HashMap. If found, you got a pair, store it in a HashSet (this will eliminate duplicates).
Time: O(n)

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

Your solution will still print (0, 4), (1, 3), (2, 2) even though (2, 2) is not a correct answer. Or am I missing something?

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

hero's sol is correct ...(2,2) will not be printed

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

Just an intern is right , vikx you are wrong here.
Hero is first storing all values in HashMap , instead he should store the value only when N-x is not found in the HashMap.Only then , (2,2) will not be printed.

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

Below are steps:
1) store all value in hasmap
2) on iterating the array before checking the value n-input[i] remove the input[i] .on next iteration first put the elemnts in map .then go for next element in array

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

Solution in Python

``````def FindPairs(array,N):
map={value:index for index,value in enumerate(array)}
pairs={(elem,N-elem) for elem in map if N-elem in map and elem>=N-elem}``````

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

Same solution in C++. Algorithm is same as hero's, linear time average complexity. Using unordered_map for true hash map and hast set at the same time.

``````std::unordered_map<double,double> FindPairs(std::vector<double>& input, double N){
std::unordered_map<double,double> i2v;
std::unordered_map<double,double> pairs;
std::for_each(input.begin(),input.end(),[&](double val){ i2v[val]=N-val;});
for (auto elem : i2v)
if (i2v.find(elem.second)!=i2v.end())
if (elem.first>=elem.second)
pairs.insert(elem);
return pairs;
}``````

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

Doesn't work for [1, 2, 3]. Returns (2, 2) as well, which it should not.
Edit the 3rd line to this

``pairs={(elem,N-elem) for index,elem in enumerate(array) if N-elem in map and elem>=N-elem and map[N-elem] != index``

}

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

Time Complexity - O(n)

2 pointer approach. one starts at the end of the array and other at the end.

1) if sum ( a[first pointer] , a[second pointer]) > N move second pointer left
2) if sum ( a[first pointer] , a[second pointer]) < N move first pointer right

keep moving untill 2 pointers meet each other.

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

This is a good idea, efficiently.

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

what if sum ( a[1st pointer], a[2nd pointer] ) == N?

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

how s dis O(n)
e.g . N =5 (5, 4,2, 3, 0, 1)
P1 =5 P2 =1 -- P2 =0 check
P1 =4 P2 = 1 - check

this way it ll be n^2 times ???

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

Let me rewrite the array to {1,2a,2b,2c,3}
Shall we return (1, 3) (2a, 2b) (2a, 2c) (2b, 2c) ?

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

This code also takes care of duplicates, unlike most of the solutions given here

``````arr=[0, 1, 2, 2, 3, 4, 5]
N = 4
map = {}
for num in arr:
if N-num in map:
print((num, N-num))
map[num] = True``````

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

How long do you think that it's appropriate to think about this question ? And how long to write it?

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

10 minutes should be more than enough think of and code up a hashtable solution.

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

The pairs only contain 2 numbers? Can it have more or less than two numbers?

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

for(int j=0;j<=num-1;j++)
{
int val=i[j];
int temp=num2-val;
for(j=0;j<=num-1;j++)
{

if(temp==i[j])
System.out.println("["+val+","+temp+"]");
}

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

Is this solution O(n^2) complexity or I am wrong?

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

1. if you sort the array , then the running time is at least 0(nlogn).
2. Is all the number positive ?
if it was, we could count the appearance of 0,1,...N in O(n) running time, and let p(i) be the frequency of i , since 0+N==N,1+(N-1)==N,...then we have min(a(i),a(N-i)) pairs of (i,N-i);
if there're negative numbers, in O(n) running time(the first scannning) we can get each of them,and you can store its frequency too, the remaining similar. While you may scan the array twice, you still got the 0(n) running time.

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

Could you explain your algo with an example ? considering -ve numbers

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

#include <stdio.h>
#define MX 7 //max no of array
//target is value sum value
//let assume given array sequence[MX] ={0, 1, 2, 2, 3, 4, 5};//assuming array is not sorted
int main()
{
int array[MX];
for(count = 0; count<MX;count++)
{
array[MX] = 0;
}
for(count = 0; count<MX;count++)
{
array[sequence[count]] = 1;
}
for(count = 0; count<MX;count++)
{
index = target - sequence[count];
if(index > 0)
{
if(array[index] == 1)
{
print(pair(sequence[count],index));
array[index] = 0;
array[sequence[count]] = 0;
}
}
}
return 0;
}

complexity : 0(n)

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

public class PrintPairsThatSumUpToValueInArray {

public static void main(String[] args) {
PrintPairsThatSumUpToValueInArray pps = new PrintPairsThatSumUpToValueInArray();
int[] array = { 8, 0, 1, 2, 2, 3, 3, 3, 4, 5, 1, 4, 6, 4, 4, 4, 5 };
int TARGET_SUM = 10;
pps.printPairsFromMap(TARGET_SUM, map);
}

Map<Integer, Integer> map = new HashMap<>();
for (int val : array) {
if (map.containsKey(val)) {
int count = (Integer) map.get(val);
map.put(val, ++count);
} else {
map.put(val, 1);
}
}
return map;
}

public void printPairsFromMap(int targetSum, Map<Integer, Integer> map) {
Iterator<Integer> itr = map.keySet().iterator();
while (itr.hasNext()) {
int key = itr.next();
int value = map.get(key);
if (key > targetSum)
continue;
int diff = targetSum - key;

if (!map.containsKey(diff))
continue;
else if (key < diff) {
System.out.println("(" + key + "," + diff + ")");
} else if (key == diff && value > 1) {
System.out.println("(" + key + "," + diff + ")");
}
}
}

}

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

public static void main(String[] args) {
final Map<Integer, Integer> values = new HashMap<Integer, Integer>();
final Map<Integer, Integer> sumOfPair = new HashMap<Integer, Integer>();

final int targetVal = 4;
int key = 0;
final int[] arrayOfNums = { 0, 1, 2, 2, 3, 4, 5 };
for (int i : arrayOfNums) {
values.put(key, i);
if ((values.containsValue(targetVal - i)) && ((targetVal - i) != i)) {
sumOfPair.put(i, (targetVal - i));
}
key++;
}
Iterator<Map.Entry<Integer, Integer>> entries = sumOfPair.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.print("(" + entry.getKey() + "," + entry.getValue()+") ");
}
}

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

void printPair(int arr[],int size,int sum)
{
map<int,int> traversed;
map<int,int>::iterator it;
int i , remain;
for (i = 0 ; i < size ; i++)
{
remain = sum - arr[i];
it = traversed.find(remain);
if (it != traversed.end() && it->second > 0)
{
cout << "\n(" << it->first << "," << arr[i] << ")" ;
traversed.erase(it);
}
if(it != traversed.end())traversed[arr[i]]=1;
else (it->second)++
}

}

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

Assuming the array is sorted the following algorithm also works -

N - being the given sum.

1] Find x = sum(first , last)
2] if x = N print elts[first] and elts[last] and continue till u reach half the array.
if x < N then first++
if x > N then last--

``````public static void main(String[] args) {

int[] elts = {0, 1, 2, 2, 3, 4, 5};
int N = 4;

for (int i = 0,j=elts.length-1; i < (elts.length/2) && i!=j ;) {
if (elts[i]+elts[j] > N)
j--;
else if (elts[i]+elts[j] < N)
i++;
else {
System.out.println("(" + elts[i] + " , " + elts[j] + ")");
j--;
}
}``````

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

public static void main (String args[]){

int[] num = {0, 1, 2, 2, 3, 4, 5};
int input = 4;
find(num,input);

}

public static void find(int[] num, int input){

for(int i=0;i<num.length;i++){
for(int j=0;j<num.length-1;j++){

if(num[j]+num[i]==input){

System.out.println(num[i]+ " " +num[j] + " "+ input);
}

}
}

}

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

Sorting the array will give better time complexity than O(n^2). We can assume thant sorting is O(nlogn) + Iteration of the elements which are less than N (arr[i] + arr[j] < N) - I can not say how much time it takes, but I believe that it is better than O(n^2)

``````public class SumOfNums {
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 2, 3, 4, 5 };
int N = 4; // (x+y==4 ?)

// sort the array
Arrays.sort(arr);
int i = 0;
while (i < arr.length-1) {
int j = i+1;
while (j < arr.length - 1 && arr[i] + arr[j] < N) {
j++;
}
if (arr[i] + arr[j] == N)
System.out.print("(" + arr[i] + "," + arr[j] + "), ");
i++;
}
}
}``````

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

Time Complexity = N^2

``````void findPair(int arr[], int size, int target, map<int, int> &data)
{
for(int i=0; i<size; i++)
{
int find = target - arr[i];

for(int j=i; j<size; j++)
{
if (find == arr[j])
{
pair<int, int> p(arr[i], arr[j]);
data.insert(p);
break;
}
}

if ( arr[i] + arr[i+1] >= target)
break;
}

}``````

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

here is the best simple solution:

public void findpairs(int ary[], int sum){
map<int,int>find=new hashmap<int,int>();
int i;
for(i=0;i<ary.length();i++){
find.put(ary[i],sum-ary[i]);
}
for(i=0;i<ary.length();i++){
if(find.containsValue(ary[i]){
system.out.println("here are the pairs",+ary[i],sum-ary[i]);
}
else{
system.out.println("sorry no pairs");
}
}
}

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

In Python

``````def SumPairs(arr,num):
return [(each,num-each)for each in arr if (num-each)>0 and (num-each) in arr]``````

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

Time complexity: Worst case: (n)
Space complexity: If we want distinct pairs then Worst case: (n) else its O(1).

External methods used:
1.) void sort(int array[]); //QUICK SORT avg case running time is nlog(n)
2.) int search(int array[], int key, int lowerBound, int upperBound); //BINARY SEARCH. returns the index of the found element.

1.) implementation of Set interface. //This is to check duplicates.

``````public void printPairs( int array[], int sum){

MySet set = new MySet();
int remainder;
int found = false;
int lowerBound = 0;

sort(array);
for( int i = array.length -1; i >= 0; i--){

if(k > array[i]){

remainder = k - array[i];
int index = search(array, remainder, lowerBound, i);

if(index > -1){
found = true;

if(!set.contains(Math.abs(array[i] - array[index]))){

System.out.print( "("+array[i] + ",(" + array[index] + ") ");
lowerBound = index;
}
}
}
}

if(!found){
System.out.println("Sorry no pairs found.");
}
}``````

The set stores the absolute difference between the pairs. the difference and the sum (i.e. k) uniquely identifies the pair (idea is that, Xi + Yi = m, Xi - Yi = n, Xj + Yj = m and Xj - Yj = n, then i = j).

The lowerBound( prevents the binary search to check for previously checked lower numbers of the array.

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

``````int find(int a[],int start,int end,int num){
while(start<end){
if(a[start]+a[end]==num){
printf("(%d,%d) ",a[start],a[end]);
start++;
}
else if(a[start]+a[end]>num){
end--;
}
else{
start++;
}
}
}``````

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

If number is shorted other wise first short it.

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

``````import java.util.ArrayList;
import java.util.List;

public class Test {
public static void main(String[] args) {

int[] values = {0,1,1,2,3,4,5,6};
int target = 6;
outer: for(int i= 0; i<values.length; i++){
int sum = values[i];
List<Integer> sequence = new ArrayList<Integer>();
inner: for(int j = (values.length -1); j>i;j--){
sum = sum+values[j];
if(sum > target){
sum = sum-values[j];
continue inner;
} else if(sum <= target){
if(sum == target){
System.out.println(sequence);
sum = values[i];
sequence.clear();
}
}
}

}
}
}``````

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

Time Complexity = O(logN), if its sorted Array
package careerCupJava;

public class SumWith2Numbers {

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

int arry[] = {0,1,2,2,3,4,5};
int i=0, j=arry.length - 1;
System.out.println("j="+j);
int sum=4;
while(i <= j)
{
int k = sum-arry[i];
if(k == arry[j])
{
System.out.println("pair pair="+arry[i]+arry[j]);
i++;
j--;
}
if( k < arry[j])
{
j--;
}
}

}

}

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

``````# include <stdio.h>
# include <conio.h>

void all_sum_pair(int a[10],int start, int end, int suma)
{
int tempa=0;
if(start < end)
{
tempa = a[start]+a[end];
if(tempa == suma)
{
printf("(%d, %d), ",a[start],a[end]);
all_sum_pair(a, start+1, end, suma);
}else{
all_sum_pair(a, start, end-1, suma);
}
}

}

void main ()
{
int arr[10];
int i,nn,j,temp,sum;
nn=10;
sum=5;

printf("Enter 10 Numbers in a column\n");

for(i =0; i <10;i++)
{
scanf("%d",&arr[i]);
}

for(i=1;i<nn;i++)
{
for(j=i;j>0 && arr[j]<arr[j-1];j--)
{
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
for (i=0; i<10;i++)
printf("%d\n",arr[i]);

all_sum_pair(arr,0,nn-1,sum);

printf("completed");
getch ();

clrscr();
}``````

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

public class PairNumber {
public int[] array =new int[]{0,1,2,3,4,5);
public void displayPairNumber(int value){
array ={0,1,2,3,4,5);
for (int i=0;i++;i<=value){
n=value;
if (i+n=value){

System.out.println(array(i)+,+array(n));
}
if (n==i){
break; } } }

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

it seems that this is some pseudocode ... why you assuming that the array is sorted? this will require at least n.logn + n running time

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

Algo goes like this. Assuming array is sorted

1. point 1 reference to start of the array say i, 2nd reference to the end of the array say j
2. if a[i] + a[j] == N print pairs, else if a[i] + a[j] > N j-- else if a[i] + a[j] < N i++ till i < j

Thinking of better approach for un-sorted array

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.

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

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