Amazon Interview Question Software Engineer / Developers
This can be done using a hashtable. For each number, check if (value - array[i]) exists in the hash, if not then add array[i] in the hashtable. Keep going through the array, until you find the pair which adds up to the value given. For example: if value = 20 and array is: 2, 15, 8, 10, 18. Start from 2, (20-2)=18, Check is 18 exists in the hashtable, if no, then put(2) into the hashtable. Go to 15, then 8, then 10 and then finally when you come to 18, check (20-18) = 2 exists, it does,return 2 and 18. This can be done in O(n) with extra storage.
This algorithm will not work correctly for all data sets as described. Consider the following minor change to the example data: 18, 2, 15, 8, 10, 18, the only difference is 18 has been inserted at the front. Start from 18, (20-18) = 2, check if 2 exists in the hash-table, if not, then put (18) into the hash-table. Go to 2, (20-2) = 18, check if 18 exists in the hash-table, it does so add the pair 2, 18. Continue to, 15, 8, 10, putting (15, 8, 10) into the hash-table. At 18 check if (20-18) = 2 exists in the hash-table, it does not so put (18). It fails at this point because the value 2 was not added to the hash-table so the second pair of 2 and 18 is lost. One way to resolve this is to sort the array: 2, 8, 10, 15, 18, 18, in this case the algorithm as described by Tom works correctly and gives two pairs of 2 and 18, but would no longer be O(n). A better alternative and Tom may have intended this but didn’t state it specifically, is to put each value into the hash-table as you iterate through the array, even if the value is already in the hash-table. This shouldn’t have any significant computational cost, assuming insertions into the hash-table are O(1), so you should still have an O(n) algorithm. The only twist is the implementation of the hash-table needs to not only return if the value exists but also how many and the position of each value in the array so you can correctly identify all matching pairs. A hash multimap meets this requirement and is easy to implement. The following pseudo code describes the algorithm.
for (each element i in the array) do
{
difference = value-array[i]
if (difference is in the hash multimap ) then
{
Iterate through all nodes==difference and
note the corresponding pairs
}
Insert array[i] into the hash multimap
}
1-first sort the array
2-then take two pointers say first and last
while(first<last)
do
if(arr[first]+arr[last]<sum)
first++
else if(arr[first]+arr[last]>.sum)
last--
else
print both numbers
done
Take this case Input = [1,2,3,4,5,5,6,7,8] and the desired sum is 10. In that case the above algo will fail because after printing input[last] = 8, and input[first] = 2, the pointers last and first are neither incremented nor decremented. Since the loop runs till first<last, this would lead to an infinite loop.
A small change to the above algo would be incrementing the first pointer in the else part.
1-first sort the array
2-then take two pointers say first and last
while(first<last)
{
if(arr[first]+arr[last]<sum)
first++
else if(arr[first]+arr[last]>.sum)
last--
else
print both numbers
first++; // or equivalently last--
}
Can anyone see any loopholes in the above algorithm ?
For all the sorting guys, remember you need to record the index of each element before you sort the array.
Since you have sorted it, check the maximum and minimum against the value first to see if you need to do something else.
Hashtable does not make sense if you do define its range or hash function.
Global(n,m,k,A[n]);
void main()
{
SORT(A);
for(i=0;i<n;i++)
if(A[i]>k)
{
n=i-1;
break;
}
for(i=0;i<n;i++)
{
if(A[i]==k)
{
PRINT(A[i]);
break;
}
if(A[i]>k)
break;
if(A[i]<k)
{
sum= A[i];
m=0;
Pair(i+1,sum);
if(m==1)
PRINT(A[i]);
}
}
}
void Pair(int p, int add)
{
for(int i=p;i<n;i++)
{
if(add+A[i]==k)
{
m=1;
PRINT(A[i]);
return;
}
if(add+A[i]<k)
{
Pair(i+1,add+A[i]);
If(m==1)
{
PRINT(A[i]);
return;
}
}
If(add+A[i]>k)
return;
}
}
Well... he seems to be returning the first time he finds a pair. And he seems to do the 'add array[i] to hash' only if value - array[i] is not in the hashtable.
ok?
Hashing will give all pairs in o(n) time and o(n) space.
For sorting and finding all pairs, you cant do this is o(n) time, in worst case it will be o(n2).
This solution runs in O(N log N)
public static void findPairs(int[] a, int val){
for (int i = 0; i < a.length; i++) {
int diff = Math.abs(val - a[i]);
if(BinarySearch.search(a, a.length, 0, diff) != Integer.MIN_VALUE){
System.out.println(a[i] + ", " + diff);
}
}
}
another way might be...
int size = array.size;
for(int index = 0; i< size; i++)
{
for(int j = i+1; j< size; j++)
{
if(array[i] + array[j] == k)
{
System.out.println(array[i] + "+" + array[j] + "are equal to " + k);
}
}
}
If the Numbers are given DISTINCT, then this'll work
1) sort array a
2) first = 0, last = a.size()-1
3) while ( first < last)
3.0) sum = a[first] + a[last]
3.1) if(sum == k )
3.15) printf a[first],a[last]
3.2) first++;
3.3) last--;
3.4) else
3.5) if ( sum > k) last--;
3.6) else first++;
4) end
#include <list>
#include <iostream>
using namespace std;
int main()
{
int intarray[]={2,4,5,3,7,8};
list<int> mylist;
list<int>::iterator it;
list<int>::reverse_iterator rit;
mylist.assign(intarray,intarray+6);//assiging the numbers from the given array.
int first=0;
int last=mylist.size()-1;
mylist.sort();//sorting the list.
cout<<"Enter the target number"<<endl;
int targetsum;
cin>>targetsum;
it=mylist.begin();
rit=mylist.rbegin();
while(first<last)
{
if((*it)+(*rit)<targetsum)
{
it++;
first++;
}
else if((*it)+(*rit)>targetsum)
{
rit++;
last--;
}
else
{
cout<<"Pair-->"<<(*it)<<":"<<(*rit)<<endl;
cout<<"Pair-->"<<(*rit)<<":"<<(*it)<<endl;
it++;
rit++;
first++;
last--;
}
}
/*for(it=mylist.begin();it!=mylist.end();it++)
{
cout<<*it<<endl;
}*/
}
------------------------------------------------------------------------------------------------------------------------------
Output:
Enter the target number
7
Pair-->2:5
Pair-->5:2
Pair-->3:4
Pair-->4:3
Sorting in the worst case takes O(nlog n)
Printing the pairs of numbers takes O(n)
Duplicate values are printed only once.
class Pair{
int a, b;
public pair(int a, int b){
this.a = a;
this.b = b;
}
}
public findsum(int[] a, int k){
int left=0, right=a.length-1;
ArrayList<Pair> set = new ArrayList<Pair>();
Arrays.sort(a);
while(left < right){
if(a[left] + a[right] > k){
right--;
}else if(a[left] + a[right] < k){
left++;
}else{
set.add(new Pair(left, right));
left++;
right--;
}
}
for(Pair p : set){
System.out.println("(" + p.a + ", " + p.b + ")");
}
}
Sort the array using any O(nlog(n)) algorithm.Then call the below function (O(n)) to find all qualified pairs. The overall complexity is O(nlog(n))
- Anonymous July 07, 2009//----------------------------------------------------------//
//Input:
//a is the sorted array,
//v is the target value
//n is the length of the array
//Output:
//ind1 stores the index for the first elment in qualified pairs,
//ind2 stores the index for the second elment in qualified pairs,
//--------------------------------------------------------------//
void PairSum(int a[],int v,int n,int ind1[],int ind2[])
{
int l = 0; int r = n-1;
int tempv; int i = 0;
while (l<r)
{
tempv = a[l] + a[r];
if (tempv==v)
{
ind1[i] = l;
ind2[i] = r;
++i;
if (a[r-1]==a[r])
--r;
else
++l;
}
elseif (tempv>v)
{
--r;
}
else
{
++l;
}
}
}