Amazon Interview Question Testing / Quality Assurances




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

- WgpShashank on June 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Shashank: neat.

- slimboy on June 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rafi on January 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nids on April 19, 2012 | Flag
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

- Mat on May 24, 2011 | Flag Reply
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

- Aditya on May 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mat on May 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on June 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- iloveit on June 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

o/p is

1 7
2 8
3 9

- iloveit on June 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this was shashank coded :)

- honey on October 27, 2012 | Flag
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).

- Abhi on May 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

didn't get you.

- Anonymous on May 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- RavishSunnyRoshan on June 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bruce on November 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ric on February 06, 2012 | Flag
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.

- dangerous dave on May 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good one..

- inx on August 16, 2011 | Flag
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

- Anonymous on June 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can someone please write the code?

- Anonymous on June 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- czylabsonasa on June 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@wgpshashank: good one :)

- geeks on July 04, 2011 | Flag Reply
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;
					}
				}
			}
	}

- newbie on August 09, 2011 | Flag Reply
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);

- newbie on August 09, 2011 | Flag Reply
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++)

- aziz on October 24, 2011 | Flag Reply
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");
//BufferedReader reader = new BufferedReader(System.in);
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");

}
}
}
}

- Rafi on January 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rafi on January 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rafi on January 16, 2012 | Flag
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

- Suchit on July 07, 2012 | Flag Reply
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;
}
}
}

- neha.dhilor on June 06, 2013 | Flag Reply
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]);
}
}

}
}
}

- RAJKUMAR JS on July 09, 2013 | Flag Reply
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; }
System.out.println("Not Found!");
return null;
}

- Anonymous on March 01, 2014 | Flag Reply
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;
}

- hi on April 03, 2014 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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