CareerCup

Find the size of the minimum length array, assume it's array1 size of n
loop array1 1..n
if(BST(array2, array1[i) == true) add array1[i] to the set to return

O(nlogm)


with hashtable we can achieve O(n) with size O(m)

Hi guyz, I have implemented this in java..

while(i < arr.length)
			{
				for(;j < arr1.length;)
				{
					if(arr[i] == arr1[j])
					{
						System.out.println(arr[i]);
						i++; j++;
						break;
					}
					else if(arr[i] < arr1[j])
						i++;
					else if(arr[i] > arr1[j])
					{
						j++;
						break;
					}
				}

<pre lang="" line="1" title="CodeMonkey63451" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class check {
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
//int[] arr = new int[5];
int arr[]={1,2,4,6,7,8,10,100,600,1000};
int arr1[]={1,2,3,4,5,6,8,9,10,100,200,300,400,700,1000};
int i=0,j=0,k=0;
while(i < arr.length)
{
for(;j < arr1.length;)
{
if(arr[i] == arr1[j])
{
System.out.println(arr[i]);
i++; j++;
break;
}
else if(arr[i] < arr1[j])
{
i++;
}
else if(arr[i] > arr1[j])
{
j++;
break;
}
}
}
}
}</pre><pre title="CodeMonkey63451" input="yes">
</pre>

Set<Integer> set = new HashSet<Integer>();

for (int i = 0; i < arr1.length; i++) {
set.add(arr1[i]);
}

for (int i = 0; i < arr2.length; i++) {
if (!set.add(arr2[i])) {
System.out.println(arr2[i]);
}
}

you Don't need 2 loops

let the two arrays be array1[]
array2[]
for(i=0; j=0; i< array1.length(); j<array2.length();) {
if(array1[i]== array2[j]) {
print("found the element %d", array1[i]);
} else if (array1[i] < array2[j]) i++;
else j++;
}

Hi

This is like merging sorted sub-arrays but with i++ and j++ when looking at the same elements.
But I dont get why for each i, Anonymous looks at every other j ?

Is that necessary ?

How about this:

while(i<A.length && j<B.length){

	int a = A[i];
	int b = B[j];
	
	if(a > b)
		j++;
	else if(a < b)
		i++;
	else
		return a;
}

if extra space is given to us we can do it in o(n lgn)
but if not we have to do it inthe 0(nm) solution :)
step 1.
first ort these 2 given sets in the 0(nlgn) time.
after sorting it should be like:)
void printintersectelement(int a[],in b[],int n,int m)
{
int i=0,j=0;
while(i<=n-1)
{
for(;j<m-1;)
{
if(a[i]==b[j])
{
printf("%d",a[i]);
i++;
j++;
break;
}
else if(a[i]<b[j])
{
i++;
break;
}
j++;
}
}

}

For Intersection of 2 arrays,
1. Maintain 2 BitSets one for each array. Size of this bitset wud be the value of largest number present in each array. Size= O(1) Time=O(1)

2. XOR the 2 bitsets . Final result wud contain 0's for the intersection values. Report them

Time complexity:O(m+n)
Space complexity: O(1)