Amazon Interview Question
Testing / Quality AssurancesNice coding, but It will fail in this case
1,2,3,4,4,5 and the number to match difference is 2
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++;
}
}
@ 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
{{
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)
ridiculous solution! it will work only for sum ie a+b=k. difference will decrease irrespective of a or b ptrs manipulated..
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);
}
}
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).
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.
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.
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
#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 ;
}
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;
}
}
}
}
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");
}
}
}
}
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;
}
#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;
}
#include<stdio.h>
- WgpShashank June 26, 2011int 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++;
}
}