CareerCup

this question has solutions now. and the time complexity is max(m*logm , n*logn). At first you should sort one of the array, then use a 'for' loop for the other array, using binary search, to every element, it will use logm or logn time. and the space complexity is o(1). And your question is the simple one, the other one is can you find all the common elements in two arrays.

Sort the list, search with a bool[]?

public boolean sharedElem(int[] aList,int[] bList){
		Arrays.sort(aList); Arrays.sort(bList);
		
		int maxElem = aList[aList.length-1] > bList[bList.length-1] 
				? aList[aList.length-1] : bList[bList.length-1];
		
		boolean[] hasElm = new boolean[maxElem+1];
		
		Arrays.fill(hasElm,false);
		for(int i = 0; i < aList.length;i++){
			hasElm[aList[i]] = true;	
		}
		for(int j = 0; j < bList.length; j++){
			if(hasElm[bList[j]])
				return true;
		}
		return false;
	}

The complexity should be max(mlogn,nlogn)? If there are duplicates in the arrays, this would not work.

we use hash, but with following data structure

struct data_item
{
    bool present;
    int count;
   data_item()
   {
       present = false;
       count = 0;
   }
};
hash_map<int , data_item> *comp;

where int is item, and structure data_item tells us about weather an item is present or not, if it present then how many time it is,
Now while comparing we always check

for each input
    if(comp(item)->present)
        comp(item)->count--;
        and go to next input
   else
       output not same
       return;
output same;
return;

Algorithm:
I. iterates array1 and add into hash map <value, occurrence>;
E.g. for 3rd and 6th index (8), hash value will be <8, 1> and <8, 2>
2 .iterate array2 and check whether that value exist or not, if yes then reduce the occurrence by 1 .if not, return false;
3. Iterate the whole hash map if the all values occurrence is 0 then return true else return false;

The greatest value of the two arrays is 8, thus a byte is sufficient to represent the existence/non-existence of all the values in either array.
To verify whether two arrays contain a set of value, mask the two corresponding bytes and & them together

This question has very elegant solution. Take one variable var = 0. Take XOR of all the elements in first array and second array with var. If the final answer is zero than both the arrays contain same elements, otherwise not.

two solution :
1 : sort both, O(max(nlogn,mlogm)); where n and m are the size of arrays;
and then compare with avoiding duplicate's, O(n+m);
total time complexity : O(max(nlogn,mlogm))
2 : use hashing in following way has_map<int , bool>, where int represent data item, and bool variable represent weather an data item is present or not ?
we start reading array one, and if an element present more then once, we don't worry, the bool variable is set to true, Now we go to second array, and we check weather there exist an element in this array whose bool variable is not set, if we are able to find one, print not true, if not, then do the same by first taking second array to populate map and check first array for validation ,if we found one whose bool variable is not set true, we print not true, else we print true
time complexity : O(max(m,n));

#include<stdio.h>

int main()
{


int arr1[] = {4,5,6,3,1,2};

int arr2[] = {2,1,3,4,5,6};

int len1 = sizeof(arr1) / sizeof(int);

int len2 = sizeof(arr2) / sizeof(int);

int num = 0;

for(int i = 0; i < len1; i++){

num ^= arr1[i];
}

for(int i = 0; i < len2 ; i++){

num ^= arr2[i];
}

if(!num)
printf("ARRAYS ARE SAME");
else
printf("ARRAYS DIFFER");

}