Adobe Interview Question
Country: India
Interview Type: Written Test
1. sort B - nlogn
2. take one element from A, search for the second element in B(using binary search) - nlogn
total - nlogn
@Devendar- Dats Not Effecient ..We can Use Dynamic Programming Which will take less than nlogn
If additional space is provided then
import java.util.HashMap;
import java.util.Scanner;
public class IntwoSetsValueEqualsToAplusB {
public static void main(String[] args) {
Integer setA[]={180,84,168,171,195,42,71,164,59,118,102,135,78,110,204,196,136,154,30,130,3,52,29,172,33,86,27,23,214,46,110,180,131,63,136,112,105,208,62,165,113,165,85,191,60,75,173,197,14,203,112,18,41,142,191,74,13,4,98,13,51,208,193,182,57,115,80,163,110,143,114,8,93,200,199,154,61,158,137,76,147,35,94,188,178,70,49,191,75,147,205,126,141,184,94,198,85,174,146,195};
Integer setB[]={84,71,102,89,87,78,6,6,7,8,89,9};
int value=new Scanner(System.in).nextInt();
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
hm=buildmap(setB);
for(int i:setA) if(hm.containsValue(value-i)) System.out.println(i);
}
private static HashMap<Integer, Integer> buildmap(Integer[] setB) {
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
for(Integer i:setB) hm.put(i.hashCode(),i);
return hm;
}
}
Solution depends on set implementation. If set is implemented using a bst or a red black tree then no sorting is required at all. Locate element greater than equal to sum in a. Now all children are less than equal to the sum. Do the same for b. Now you select one element from a and find if sum - a is found in b.
1. iterate over hastSet1.
2. for every element(lets say i), check if hashSet2.contains(value - i) //where value is a + b
3. if true, return 1
Complexity:
worst case: O(n) - as complexity of contains is O(1) and iterating over hashset has O(n)
best case: O(1) - as at first element you can get elements and it returns 1 when such values are found, so return 1 over there itself.
Here is the psudo code -
for each element x in C
find a pair A[i], B[j] from A and B such that A[i] + B[j] = -x
end
The outer loop will run for O(n) and inner loop also for O(n), so total complexity will be O(n^2).
To find a pair A[i], B[j] s.t A[i] + B[j] = k.
First make i point to the start of array A and point j to the end of array B.
check -
1. If A[i] + B[j] == k, we found our elements so just exit.
2. If A[i] + B[j] > k, we have to decrease our sum. Decrement j.
3. If A[i] + B[j] < k, we have to increase our sum. Increment i.
So this will run for O(n). Thus making the complexity of the complete method as O(n^2).
int setABHasSum(int* setA, int aLen, int* setB, int bLen, int val)
{
int i, j;
int a, b;
int bExpected;
if(aLen == 0 || bLen == 0)
return FALSE;
for(i = 0; i < aLen - 1; i++)
{
a = *(setA+i);
bExpected = val - a;
for(j = 0; j < bLen; j++)
{
b = *(setB+j);
if(b == bExpected)
return TRUE;
}
}
return FALSE;
}
#include<iostream>
using namespace std;
int main()
{ int a[10]={12,9,7,5,3,2,1};
int b[10]={2,4,6,7,9,10,15};
int m;
cout<<"enter the sum value\n";
cin>>m;
for(int i=0,j=0;i<7&&j<7;)
{ int sum=a[i]+b[j];
if(sum<m)
{ j++;}
else if(sum>m)
{ i++;}
else if(sum==m)
{ cout<<a[i]<<" "<<b[j]<<endl;
i++; j++;
}
}
system("pause");
return 0;
}
If additional space is provided then
- dilip kasana September 19, 2012import java.util.HashMap;
import java.util.Scanner;
public class IntwoSetsValueEqualsToAplusB {
public static void main(String[] args) {
Integer setA[]={180,84,168,171,195,42,71,164,59,118,102,135,78,110,204,196,136,154,30,130,3,52,29,172,33,86,27,23,214,46,110,180,131,63,136,112,105,208,62,165,113,165,85,191,60,75,173,197,14,203,112,18,41,142,191,74,13,4,98,13,51,208,193,182,57,115,80,163,110,143,114,8,93,200,199,154,61,158,137,76,147,35,94,188,178,70,49,191,75,147,205,126,141,184,94,198,85,174,146,195};
Integer setB[]={84,71,102,89,87,78,6,6,7,8,89,9};
int value=new Scanner(System.in).nextInt();
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
hm=buildmap(setB);
for(int i:setA) if(hm.containsValue(value-i)) System.out.println(i);
}
private static HashMap<Integer, Integer> buildmap(Integer[] setB) {
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
for(Integer i:setB) hm.put(i.hashCode(),i);
return hm;
}
}
in O(n+m)