CareerCup

My solution without data structure is of the order O(nlogn) where A.length=n and B.length=m and n>m. Sort one of the arrays and do a binary search using the elements of the other array.

My solution with data structure is of the order O(n) where A.length=n and B.length=m and n>m. traverse the array and put it in hashmap then traverse another array check for its existence in the Hashmap.

I think without using any other data structure this could be the solution:
a.Let n and m be the size of the arrays: If m=n then traverse one of the arrays.If at any point
&arr[i]=&arr[j] then that will be the intersection point.
b.If m>n then calculate the difference as m-n. Then with the array of size m traverse the first d elements and then start a parallel traversal of both the arrays until we get the intersection point.

With data structure you can store the addresses of both the arrays in a hashmap and then during array traversal of the array with larger size if you find at any time that the address of a particular element is same then that is the intersection point..

One of the approaches to solving the above algorithm is using the binary search in a sorted array, we will first take the array elements from the first array and then search it in the second array using binary search and will make sure that the second array is sorted.

Implementation:

int binarysearch(int arr_2[], int low, int high, int key){
	if(high >= low){
		int mid = low + (high - low) / 2;
		if(arr_2[mid] == key)
			return 1;
		else if(arr_2[mid] < key)
			return binarysearch(arr_2, mid + 1, high, key);
		else
			return binarysearch(arr_2, low, mid - 1, key);
	}
	return -1;
}
int main(){
	int m, n;
	int arr_1[m];
	int arr_2[n];
	for(int i = 0; i < m; i++)
		cin>>arr_1[i];
	for(int i = 0; i < n; i++)
		cin>>arr_2[i];
	sort(arr_2, arr_2 + n);
	for(int i = 0; i < m; i++){
		if(binarysearch(arr_2, 0, n - 1, arr_1[i]) == 1)
			count++;
	}
	cout<<count<<endl;
	return 0;
}

Also we can do it using a data structure named hashset or unordered_set and insert the array elements of the first array and then, check for the common elements in the second array using elements stored in the hashset.

public static void intersectiongArray(){
int[] a = {1,2,3,4,5};
int[] b = {6,5,2,7,2};

boolean[] c = new boolean[256];
for(int i =0; i<a.length;i++){
int ascii = a[i];
if(!c[ascii]){
c[ascii] = true;
}
}
for(int j=0; j<b.length;j++){
int ascii = b[j];
if(c[ascii]){
System.out.println(b[j]);
}
}
}

public static void intersectiongArray(){
int[] a = {1,2,3,4,5};
int[] b = {6,5,2,7,2};

boolean[] c = new boolean[256];
for(int i =0; i<a.length;i++){
int ascii = a[i];
if(!c[ascii]){
c[ascii] = true;
}
}
for(int j=0; j<b.length;j++){
int ascii = b[j];
if(c[ascii]){
System.out.println(b[j]);
}
}
}

Can we create a BST with one set of array and then traverse through the other set of elements for its existence ? Should take O(nlogn)

How to do this when the arrays are relatively huge? Suppose array A is in a disk and array B is in another disk. How do we find out A intersection B efficiently?

Simple and clean solution. Cross checked it works.

void intersection(int *a, int*b, int len1, int len2) {
312         /*sort the arrays*/
313         sort_array(a,0,len1);
314         sort_array(b,0,len2);
315 
316         while (len1>=0 && len2>=0){
317 
318                 if(a[len1] > b[len2])
319                         len1--;
320                 else if (a[len1] < b[len2])
321                         len2--;
322                 else{
323                         printf("%d ",a[len1]);
324                         len1--;
325                         len2--;
326 
327                 }
328 
329         }
330 }

Without using another data structures, we can quick sort the second array in O(nlogn), and for each element in the first array, we do binary search on the second sorted array. The time-complexity is O(mlogn), where m is the length of the first array and n is the length of the second array.

If we could use a HashMap, under no collision assumption, the time-complexity would be O(max(m, n)).

public static int binarySearch(int[] a, int value, int l, int h) {
    if (l <= h) {
      int mid = (l + h) >> 1;
      if (a[mid] == value) {
        return mid;
      } else if (a[mid] < value) {
        return binarySearch(a, value, mid + 1, h);
      } else {
        return binarySearch(a, value, l, mid - 1);
      }
    } else {
      return -1;
    }
  }
  
  public static void printIntersection(int[] a, int[] b) {
    java.util.Arrays.sort(b);
    for (int i = 0; i < a.length; i++) {
      if (binarySearch(b, a[i], 0, b.length - 1) != -1) {
        System.out.print(a[i] + " ");
      }
    }
  }

My solution is uses the algorithm used to merge 2 arrays often seen in merge sort with a slight change.

In that algo, when the current heads of the 2 arrays are equal move the common value to a new array(say arr1) when full traversal will be made arr1[] will contain the intersection of the 2 arrays. Since it takes one single traversal its complexity is O(n)

This is equal to finding the intersecting node for two linked lists.