CareerCup

the most efficient solution is using hashtable for the 1st array.

#include <set>
#include <algorithm>
#include <iostream>

using namespace std ;

int main() {

	int a[] = {1,2,3,4,5,6} ;
	int b[] = {3,4,7,1,9} ;
	
	set<int> mySet(b, b+5) ;
	
	cout << "\n Intersection :\t " << std::endl ;
	
	for(int i=0 ; i<6; ++ i ){
		if(std::binary_search(mySet.begin(), mySet.end(),a[i] ) )
			std::cout << a[i] << "\t" ;
	}		

	return 0 ;
}

The interviewer needed a solution code using hashtable...can anyone write the code usage..i coudnt. Thanks.

To use hashtable, you should know the range of elements present in the array, I think.

He asked me to consider a general input, not a given arrays.

int findDup(int arr[], int arr2[]){
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0;i<arr.length;i++){
map.put(arr[i],i);
}


for(Integer i :arr2){
if(map.contains(i))
return map.get(i);
}

return -1

}

Thanks. And can the union of the two arrays be implemented with hashtables? If so, can you please give me the implementation for it.

@cacheMachine..I understand in your code is that you are creating a hashmap called map and adding all the arr[] values into it. When you write map.put(arr[i],i); , are the array elements added as keys or values?

And are you checking if the keys are same or the values as you have not mentioned if its is map.containskey() or map.containsvalue().

somebody plz tell me ...wht is meant by intersection of arrays??

package practice;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;

public class IntersectionOfArrays {

public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr = {3,6,7,4,9};
int [] brr = {2,8,1,7,0};
Hashtable ht = new Hashtable();
for(int i=0; i<5; i++)
{
ht.put(arr[i], i);
}
for(int i=0; i<5; i++)
{
int a;
a= brr[i];
if(ht.containsKey(a))
{
System.out.println("the array intersect");
}
else
{
System.out.println("the array does not intersect");
}
}

}

}

Sort one of the arrays with quick sort O(n*Log(n)).
Loop through the other array and if item exists in the other array include it in result(O(n*Log(n))

The algorithm will be O(n*Log(n)