## Amazon Interview Question for Testing / Quality Assurances

• 0

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

#include<stdio.h>

int main()
{
int arr[9]={10, 14, 17, 22, 23, 25, 26, 27, 45};
int i = 0;
int j = 1;
int num = 2;
while(j<9)
{
if(arr[j] - arr[i] == num)
{
printf("two numbers whose difference is equal to num are %d %d",arr[i],arr[j]);
i++;j++;
}
else if((arr[j]-arr[i])>num)
i++;
else if((arr[j]-arr[i])<num)
j++;
}
}

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

@Shashank: neat.

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

Nice coding, but It will fail in this case
1,2,3,4,4,5 and the number to match difference is 2

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

This might solve the problem pointed out by Rafi.. and also makes the code a little more efficient. I took Shashank's code to make minor changes to it. Thanks Shashank for sharing the neat code.

int main(){
int arr[9] = {10, 17,19, 22, 23, 25, 26, 27, 45};
int i = 0, j = 1;
int num = 2;
while(j<9){
if(arr[j] - arr[i] == num){
cout << "two numbers whose difference is equal to "<< num << " are "<< arr[i] <<" and "<< arr[j] << endl;
i++;
j++;
}
else if((arr[j]-arr[i])>num){
i++;
if (i == j)
j++;
}
else if((arr[j]-arr[i])<num)
j++;
}
}

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

Same question as finding a, b from array that sum to target. Have two index one pointing to 0, and the other at n-1. Increment/decrement pointers accordingly to current value at pointers

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

@ mat I am not getting how you are relating these questions in this case whether you increment or decrement the difference is gonna decreased....

I think this can be done in nlog(n)

1. take the first element in an array and assume it that this cold be the one of two numbers.
2. If this is the other number then other number would the sum of difference and this number.
3. do a binary search for this number(difference + assumed number) if it has been found then these are the two numbers otherwise take the 2nd number and repeat the process again till find you find the two numbers

If you have better soln then please comment

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

{{
Let me write the algorithm so it will be clear

int a = 0, int b = 1;
boolean found = false;
while(a != arr.length-1 && !found && b < arr.length)
{
if(arr[b] - arr[a] == target)
found = true
else if(arr[b] - arr[a] < target)
b++;
else
{
a++;
if(a == b)
b++;
}
}
}}
Time O(n)
Space O(1)

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

ridiculous solution! it will work only for sum ie a+b=k. difference will decrease irrespective of a or b ptrs manipulated..

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

I don't see whats wrong with this, on similar lines in java

``````import java.lang.Object;
import java.util.*;
import java.util.Arrays;
import java.util.ArrayList;
/*given an array and find two numbers in the array having difference equal to given number.i am also given that arr is sorted
11
*/
public class Arraydiff {

public static void findnumbers(int no, int[] a)
{
int p1= 0;
int p2= 0;
boolean found= false;
while(p1<a.length-1&&p2<a.length-1)
{
if (a[p2]-a[p1]==no)
{
found= true;

System.out.println(a[p1]+ " "+a[p2]);
p1++;
}
if(a[p2]-a[p1]>no)
{
p1++;
}
if(a[p2]-a[p1]<no)
{
p2++;
}
if(a[p2]-a[p1]==0)
{
p2++;
}

}

}
public static void main(String args[])
{
int[] a ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
findnumbers(6,a);

}

}``````

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

o/p is

1 7
2 8
3 9

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

this was shashank coded :)

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

You can do it in order 2n create an array with negation of all the arrays and put it before the original array
suppose a1,a2,a3,....aN was you original array then new array will be
-aN,.....-a2,-a1,a1,a2,a3......,aN
Now find in this array if sum of any two elements is equal to given number. That is an standard algorithm in O(N).

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

didn't get you.

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

how the sum of 2 numbers in the new array can be calculated in O(N) time??

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

This is good. difference can be calculated by summing the number's negative.

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

As it is a sorted array, we don't need to create the 2nd array to do the job. What we need is two pointers, point from the start and the end of the array and moving towards each other. This can solve the problem in O(n).

Another way is to use binary search to locate the position for the 2nd pointer, which will have better performance.

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

in this care. Same as finding elements with a given sum. In this case have one pointer pointing first element and another pointer pointing second element. If difference is less than expected move second pointer to the right or move the first pointer to the right.

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

good one..

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

hashing can prove useful here
1.make a hash table with the number entries
2traverse from left to right and for each value check wether the number + difference is in has table or not

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

Can someone please write the code?

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

``````#include <algorithm>
using std::lower_bound ;
#include <iostream>
using std::cout ;
using std::cin ;

// assumptions:
// x is given in ascending order
// y is nonnegative
// complexity log(n!) :)

template < typename T > void F( T * x , int nx , T y )
{
// search for two distinct index i , j such that x[ j ] - x[ i ] = y
int i = 0 ;
int j ;
bool found = false ;
while( i < ( nx - 1 ) )
{
T yy = x[ i ] + y ;
// one can check here for yy <= x[ nx - 1 ] ...
j = ( lower_bound( & x[ i + 1 ] , & x[ nx ] , yy ) - x ) ;
if( ( j < nx ) && ( x[ j ] == yy ) )
{
found = true ;
break ;
}
i += 1 ;
}

if( found )
{
cout << i << " " << j << "\n" << x[ j ] << " " << x[ i ] << "\n" ;
}
else
{
cout << "nope\n" ;
}
}

int main()
{
int nx ; cin >> nx ;

typedef int T ;
T * x = new T[ nx + 1 ] ;
for( int i = 0 ; i < nx ; cin >> x[ i ++ ] ) ;
T y ; cin >> y ;
F( x , nx , y ) ;

return 0 ;
}``````

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

@wgpshashank: good one :)

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

1.I'm new to java. Please check if the following solution appropriate. I my approach I first checked if the array is Ascending or Descending

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

//	int [] arrr = {1,3,4,6,5,7,8,9,12,13,14,16,17,19};
int [] arrr = {20,18,15,13,11,10,9,7,5,3,2,1};

int s = 20;
//findSum(20,arrr);
findDiff(1,arrr);
}

public static void findDiff(int sum, int []a){

if ((a[a.length-1]- a[0])>0){
AsndArrDiff(sum,a);
}else{
DesndArrDiff(sum,a);
}

}

public static void AsndArrDiff (int sum, int []a){

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

for (int j=i-1;j>=0;j--){
if ((a[i]-a[j])==sum){
System.out.println("Numbers are : "+a[i]+" and " + a[j]);
break;
}else if((a[i]-a[j])>sum){
break;
}
}

}

}
public static void DesndArrDiff (int sum, int []a){
for (int i=0;i<a.length-1;i++){
for(int j=i+1;j<a.length;j++){
if ((a[i]-a[j])==sum){
System.out.println("Numbers are : "+a[i]+" and " + a[j]);
break;
}else if((a[i]-a[j])>sum){
break;
}
}
}
}``````

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

Kindly ignore the following two lines I've mentioned in the main method(previous post)

int s = 20;
//findSum(20,arrr);

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

Have two indexes at the first 2 numbers in the array. Each step
index1=0
index2=1
if arr[index2]-arr[index1] = diff FOUND
if arr[index2]-arr[index1] < diff index2++
if arr[index2]-arr[index1] > diff (index1++ if index1=index2 index2++)

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

public class MainClass {
public static void main(String[] arg){
int[] numbers = {1,2,4,5,12,15,18};
System.out.println("Enter the Number to get the two arrays giving that difference");
int input = 3;
finddiff(numbers,input);
}

public static void finddiff( int[] numbers, int input)
{
int length = numbers.length;
//int maxlength = 0;
for (int i=0; i<length-1; i++)
{
for (int j=1; j<length; j++)
{
if ( numbers[j] - numbers[i] == input )
System.out.print("numbers "+numbers[i]+" in position "+i+" and "+numbers[j]+" in position "+j+" gives the difference "+input+"\n");

}
}
}
}

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

for (int j=1; j<length; j++) should be for (int j=i; j<length; j++)

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

for (int j=1; j<length; j++) should be for (int j=i+1; j<length; j++)

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

1. Sort the arrayList
2. Create a BST
3. Start at root, and find a node whose value equals (sum - root). If you find the node, delete root and the node

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

Kindly suggest if the following code will correctly:
If array is :
int [] arr=new arr[1,3,8,13,15]
int no; //can be anything

public static void main(string[] args)
{
for (int i=0;i<=5;i++)
{
for (int j=i+1;j<=5;j++)
{
if(arr[j]-arr[i]==no)
{
return true;
}
return false;
}
}
}

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

class Practice{
public static void main(String[] args)
{
int num = 3;
int array[] = {4,2,7,4,5,5,1};

for (int i = 0;i<array.length;i++)
{
for(int j=0;j<array.length;j++)
{
if (array[j]-array[i]==num)
{
System.out.println("The nubmers are "+array[j]+" and "+array[i]);
}
}

}
}
}

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

public static int[] findNumber(int[] array, int sum) {
int[] result = new int[2];
result[0] = 0;
result[1] = array.length - 1;
while ((array[result[1]] - array[result[0]]) != sum && result[0] != result[1]) {
if ((array[result[1]] - array[result[0]]) > sum) result[1]--;
else result[0]++;
}
if ((array[result[1]] - array[result[0]]) == sum) { return result; }
return null;
}

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

#written in perl and works fine. \$cmp

``````@arr=(1,4,5,6,7,9,11,22,33,44,44,45);
\$cmp=@ARGV[0]; #pass the value of difference you want at cmd line argument
foreach(@arr)
{
print "\$_ \t";
}
#\$cmp1=-\$cmp;
\$i=0;
\$j=0;
while(\$i<@arr)
{
while(\$j<@arr)
{
if(\$i==\$j)
{
\$j++;
}
if((@arr[\$i]-@arr[\$j]==\$cmp)||(@arr[\$i]-@arr[\$j]==-\$cmp))
{
print "arr[\$i] @arr[\$i] minus arr[\$j] @arr[\$j] is equal to \$cmp \n";
\$j++;
}
else
{
#print "arr[\$i] is @arr[\$i] and  arr[\$j] is @arr[\$j] and there sub is not equal to \$cmp \n";
\$j++;
}
}
\$i++;
\$j=0;
}``````

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.