Amazon Interview Question
Site Reliability EngineersCountry: United States
This approach will return the same pair multiple times. The question asks for unique pairs. You need some way of knowing which values have already been used. Maybe a bit-vector.
To solve the problem of duplicate pairs, for the pair of ith element do binary search from i+1 to N.
sorry i forgot to mention that you have to search only in i+1 to n elements . I have edited the answer.
Cool, but what if there are duplicated values in the input?
eg., input = {2, 2, 6}, and desired sum is 8. the algorithm would return the pair (2, 6) twice.
While iterating the element you just have to chek the adjacent element. If the element is same then just increment the pointer to the next location.
Well, the question needs to be clarified a lot.
1. Are the elements given in the range? If yes, use look up table.
2. else, do sort the array in nlogn, remove duplicates & find the pairs by running the two pointers, low[=0] & high[=n-1].
3. Are the pairs {2,6} & {6,2} considered the same?
Below code is based on: 1 & 3
void findPair(int* a,int n,int k)
{
int hash[10]={0},i;
for(i=0;i<n;i++)
{
if(!hash[a[i]])
{
if(hash[k-a[i]])
printf("%d %d\n",a[i],k-a[i]);
else
hash[a[i]]=1;
}
}
}
complete code here: ideone.com/17w1Z
import java.util.HashMap;
public class GetPairValue {
void findPair(int Sum)
{
HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
int[] a={2,4,6,4,7};
for(int i=0;i<5;i++)
{
if(hm.get(a[i])==null)
{
hm.put(a[i], Sum-a[i]);
}
}
System.out.println(hm);
for(int i=0;i<5;i++)
{
if(hm.get(a[i])!=null && hm.get(hm.get(a[i]))!=null)
{
System.out.println("Pair Values are : "+a[i]+" "+hm.get(a[i]));
hm.remove(a[i]);
hm.remove(Sum-a[i]);
}
}
}
public static void main(String str[])
{
GetPairValue gpv=new GetPairValue();
gpv.findPair(8);
}
}
is it necessary to do two traverse?
public void findUniquePairSumToN(int n) {
Map<Integer, Integer> table = new HashMap<Integer, Integer>();
for (int a : array) {
if (table.containsKey(n - a)) continue;
table.put(a, n - a);
}
for (Map.Entry<Integer, Integer> entry : table.entrySet()) {
System.out.println("Pair: " + entry.getKey() + " " + entry.getValue());
}
}
#include<stdio.h>
#include<stdlib.h>
int a[10];
void sum(int a[10], int i, int j, int n, int s)
{
if(i == n)
return;
if(j == n)
return sum(a, i+1, 0, n, s);
if(s == a[i] + a[j] && i != j)
{
printf("\n\nPairs are {%d and %d}\n\n", a[i], a[j]);
a[j] = -5000; //---- Just to avoid the repetative pairs. Example: (2,4) and (4, 2).
sum(a, i+1, 0, n, s);
}
else
sum(a, i, j+1, n, s);
}
int main()
{
int i, n, s;
printf("\nEnter the number of elements\n");
scanf("%d", &n);
printf("\nEnter the sum\n");
scanf("%d", &s);
printf("\nEnter the elements\n");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
sum(a, 0, 1, n, s);
system("pause");
return 0;
}
int array[]={10,20,30,40,50,60,70,80};
n=8;
cout<<" \n\nEnter the value :";
cin>>val;
int flag=0;
i=0,j=n-1;
while(i<j)
{
if(array[i]+array[j]==val)
{
cout<<"\n"<<array[i]<<" + "<<array[j]<<" = "<<val;
flag=1;
i++;
j--;
}
else if(array[i]+array[j]>val)
j--;
else
i++;
}
if(flag==0)
cout<<"\nNo such elements";
I tihnk it is not necessary that only two elements will sum up to the given sum S.isnt it??
sorry i mis read this question works for the given input but fails for this input array :
array[]={2,5,3,4,6,1};
I think it cant be done in O(n) , you have to take two loops .
see this : ideone.com/TVwTX
your algo is expecting numbers in sorted order and unique elements in the list. take this example and solve it { 2,4,6,2,4,6}
you have to sort your array first. so time complexity will be O(nlgn).
it can be done using hashing in O(n).
Don't think hashing is a good idea, since no range for numbers is mentioned......Can end up using lots of space.....
#include <iostream>
#include <map>
using namespace std;
int main ()
{
int ar[10]={2,3,7,6,4,5,0,1,2,8};
map<int,int> mymap;
map<int,int>::iterator it;
for(int i=0;i<10;i++)
{
int a = ar[i];
mymap[a]=a;
}
// show content:
//12+25 = 37
int sum = 4;
for ( it=mymap.begin() ; it != mymap.end(); it++ )
{
int x = sum-(*it).first;
if(mymap[x])
{cout << (*it).first << "and" << mymap[x] << endl; }
}
getchar();
return 0;
}
#include <iostream>
using namespace std;
int main()
{
int givenArray[] = {7,2,4,6,4,6,1};
int answer = 8;
int count=0;
for(int i=0; i<7; i++)
{
for(int j=i+1; j<7; j++)
{
count++;
if(givenArray[i]+givenArray[j] == answer)
cout<<"{"<<givenArray[i]<<","<<givenArray[j]<<"} => index("<<i<<" ,"<<j<<")"<<endl;
}
}
cout<<"count = "<<count;
return 0;
}
Answer is:=>
{7,1} => index(0 ,6)
{2,6} => index(1 ,3)
{2,6} => index(1 ,5)
{4,4} => index(2 ,4)
count = 21
The complexity is n logn and here index does matter so pairs (2,6) at 1,3 is different then pairs of (2,6) at 1,5
Array.prototype.unique = function(){
var arr = this, new_arr = [];
console.log(arr)
for(var i=0 ; i<arr.length; i++){
if(new_arr.indexOf(arr[i])===-1){
new_arr.push(arr[i]);
}
}
return new_arr;
}
function pair(array/*array*/,sum/*int*/){
var result = {}, i=0, temp;
/*preprocessing*/
array = array.unique();
console.log(array)
while(i<array.length){
temp = sum - parseInt(array[i]);
if(array.slice(i).indexOf(temp)!=-1){
result[array[i]] = temp;
}
i++;
}
return result;
}
var array = [2,4,6,4,3,6,7,9,4,8,2,7,1];
var sum = 10;
var obj = pair(array,sum);
for(var i in obj){
document.write(i+" : "+obj[i]+"<br/>");
}
HashMap approach. The only "cool" thing is I didn't use extra data structure to prevent from printing duplicate pairs. The embedded comment should be clear on how I am using the hashmap alone to prevent printing duplicate pairs.
static void findPairs(int[] arr, int sum) {
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
for(int i : arr) {
int j = sum-i;
// suppose sum=8 and i=6, then j=2
// we want to check whether j=2 is already in the map and whether
// the value is false (indicating we haven't printed it yet)
// furthermore, we want to check whether i=6 is in the map because
// if so, then this pair must have been printed as well
// exception is when i=j, such as i=4 and j=4
if(map.containsKey(j) && !map.get(j)) {
if(i == j || !map.containsKey(i)) {
System.out.println("" + j + "+" + i);
map.put(i, true);
map.put(j, true);
}
} else {
map.put(i, false);
}
}
}
Time: O(n), Space: O(n)
public class DistinctPairs {
public static void main(String[] args) {
System.out.println(count(10, 1, 2, 3, 6, 7, 8, 9, 1) == 3);
System.out.println(count(47, 6, 1, 3, 46, 1, 3, 9) == 1);
System.out.println(count(9, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
System.out.println(count(9, 3, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
System.out.println(count(6, 1, 5, 7, -1) == 2);
System.out.println(count(6, 1, 5, 7, -1, 5) == 2);
System.out.println(count(2, 1, 1, 1, 1) == 1);
}
private static int count(int target, int... arr) {
int count = 0;
Set<String> seen = new HashSet<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
int k = target - arr[i];
int[] pair = new int[]{k, arr[i]};
Arrays.sort(pair);
String s = Arrays.toString(pair);
if (set.contains(k) && !seen.contains(s)) {
count++;
seen.add(s);
} else {
set.add(arr[i]);
}
}
return count;
}
}
You can do this in O(nlogn) time complexity.
- Deven Bhooshan July 12, 2012First sort the elements [O(nlogn)]
now start from the very first element and binary search (sum-firstelement) in i+1 to n.can be done in logn
Do so for every other number.
Overall time comlexity is still O(nlogn)
Example:
a={3,2,5,1,8,0} sum to be want 8
Sorted array={0,1,2,3,5,8};
start with 0 and binary search (8-0=8) in i+1 to n
and then start with 1 binary search (8-7) in i+1 to n
and so on :)