CareerCup

Can be done without recursion.

Something like...

i = 0;
j = 0;
  
while (i < la && j < lb) {
    if (a[i] == b[j]) {
        print(a[i]);
        i++;
        j++;
    }
     
    if (a[i] > b[j]) 
        j++;
    else 
        i++;
}

public static void insertionOfTwoArrays(int data1[], int data2[]){
		int i = 0, j = 0;
		int prev = data1[0] < data2[0] ? data1[0] - 1 : data2[0] - 1;
		while (i < data1.length && j < data2.length) {	
			if (data1[i] == data2[j] && prev != data1[i]){
				System.out.print(data1[i]+ " ");
				prev = data1[i];
				i++;
				j++;
			}
			else if(data1[i] < data2[j]){
				i++;
			}else {
				j++;	
			}
		}
	}

Use recursion..

m log n where m<n sizes

guys, I think this is how it should be., though i have not tested yet.
void intersect(int *a, int *b, int la, int lb)
{
int l;
int size;

if(la>lb)
{
l = la - lb;
size = la;
}
else
{
l = lb - la;
size = lb;
}

for(int i = l ; i< size; i++)
{
for(int j = 0; i< l; j++)
{
if(a[i]! = b[j])
return;
else
{
cout<<"Intersection element is"<<a[i];
}
}
}
}
Suggestions most welcome....

if we can recursion method so we can do that

Why recursion? o(m+n) solution appears fine.

void intersectOfSortedArrays(a,b) {
int i = 0;
int j = 0;

while (i < a.length && j < b.length) {
if (a[i] == b[j]) {
System.out.print(a[i] + " : ");
i++;
j++;
continue;
}
if (a[i] < b[j])
i++;
else
j++;
}

Since both the arrays are sorted, how about binary searching elements of smaller array(say 'a') in the bigger array (say 'b'), also skipping search for each element of 'a' which is smaller than the first element of 'b' or greater than last element of 'b'. thus giving a complexity of O(lalog(lb)) what say

Use hash table. Insert integers from a[] into this hash table. insert items from b[] again, see if a collision occurs. That is the common element. Put than in c[] which is a intersection of a[] and b[]

Algo by Ashi works.
If we wanna do by map, i guess Anonymous's method can be improved by...
hash contents of array1 with count of a particular element as the value.
iterate over array2. If element is found- check if count > 0, decrement count and write to o/p.
Example: array1: 1 2 2 5 6 6 6 , array2: 1 1 2 6 6 7 , then o/p: 1 2 6 6.
-Hash contents of first array:
val count
1 2
2 1
6 2
7 1

iterate over array2. - found 1 so check if count > 0 , decrement count , write to o/p.
Not sure if binary search will work in this case. It wud produce 1,2,6 as the result not 1, 2 , 6, 6 .

Using hash table you don't need the arrays to be sorted, so this doesn't seem good.

O(m+n) = O(2m) or O(2n) at the worst case
O(mlgn) or O(nlgm) is obviously greater than O(2m) or O(2n)

One of the most efficient algorithm to find out the intersection of two sorted arrays is to check for the following conditions which are as follows:
1. We will first check for the condition that if the element of the first array is greater than the element of the second array then, we will increment the index of the second array and the other condition will be just the opposite.
2. And the last condition will be that when the data of both are equal then we will increment the index of both the arrays.

Implementation:

void findintersection(int arr_1[], int m, int arr_2[], int n){
	int i = 0;
	int j = 0;
	while(i < m && j < n){
		if(arr_1[i] > arr_2[j])
			j++;
	        if(arr_1[i] < arr_2[j])
			i++;
		if(arr_1[i] == arr_2[j]){
			cout<<arr_1[i]<<" ";
			i++;
			j++;
		}
	}
}

@above: you have to store the an extra value to check for duplicates(assuming a number will occur only once in the intersection in case of duplicates on either side)

i = 0;
j = 0;
prev = a[0] < b[0] ? a[0] - 1 : b[0] - 1;
while (i < a.Length && j < b.Length) {
  if (a[i] == b[j] && prev != a[i])
  {
    print a[i];
    prev = a[i];
    i++;
    j++;
  }
  a[i] < b[j] ? i++ : j++;
}