CareerCup

Method 1: hashtable
space complexity: O(n). time complexity: O(n)

Method 2: sort then scan
(1) sort two arrays, O(nlogn + mlogm)
(2) use to pointers to scan the two arrays. when finding two same values, stop and return. O(n+m)
time complexity: O(nlogn+mlogm)

- eboyGTK April 15, 2012 | Flag Reply

hash contents of array1.
on second array if collision, increment value
linear search through hash and all those keys with value >1 are in both arrays

- t January 14, 2010 | Flag Reply

bool hasSame(int* a, int* b, int la, int lb){
    sort(a, la);
    sort(b, lb);
    int i=0, j=0;
    while(i<la && j<lb){
        if(a[i] == b[j]) return true;
        if(a[i] > b[j]) j++;
        else i++;
    }
    return false;
}

void sort(int* a, int la){
    int k = rand(la); // from 0 to la-1
    int spliter = a[k];
    int i=0, j=la-1;
    while(i<j){
        if(a[i]<=a[k]) i++;
        if(a[j]>a[k]) i--;
        if(a[i]>a[k] && a[j]<=a[k]){
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }
    sort(a,i);
    sort(a+i, la-i);
}

- Anonymous February 11, 2010 | Flag Reply

@ t, there is a small change in ur logic. Instead of incrementing for the 2nd array, decrement the value of hash based on 2nd array. if all the values are 0, then the arrays are similar

- Vijgan February 15, 2010 | Flag Reply

take xor of both arrays and compare ?

- Anonymous March 07, 2010 | Flag Reply

Make an assoicative array.Init to zero.
Go thru first array --> associative_array[ arr1[index] ]++ ;
Go thru second array --> associative_array[ arr2[index] ]-- ;

if all elements in associative_array are not zero, return false...

- game. March 07, 2010 | Flag Reply

what if there are repeated elements in the first array?
arr1 = {1,2,2,3}, arr2={4}
The above approaches will return {2,4} -> incorrect !

- neo March 18, 2010 | Flag Reply

Using all possible early exit points with a hash table solution suggested by @t and improved by @Vijgan. In JavaScript: {{{​Array.prototype.equals = function(other)​ { if(this.length != other.length) { return false; } var value, hash = {}; for(var i = 0; i < this.length; i++) { value = this[i]; if(typeof hash[value] == 'undefined') { hash[value] = 0; } hash[value]++; } for(var i = 0; i < other.length; i++) { value = other[i]; if(typeof hash[value] == 'undefined') { return false; } hash[value]--; } for(var key in hash) { if(hash[key] != 0) { return false; } } return true; };}}] {{{[1,2,3].equals([3,1,2]) // true [].equals([]) // true [1,3,55].equals([3,55]) // false}}} - Anurag June 30, 2010 | Flag Reply

Can we take sum and product for both arrays and compare?

- Nams September 17, 2010 | Flag Reply

xor elements of A first, if result is 0, this will be useless. if not 0 keep xoring elements of B if you get 0 they are equal.

- dantepy May 18, 2011 | Flag Reply

Following two steps, both must be true
1)find sum of individual arrays, both sums must be equal
2)Now xor both the arrays, xor must be 0

If both above conditions are satisfied,arrays contain same elements
Complexity: O(n)

- Anonymous June 25, 2012 | Flag Reply

Take XOR of both array if contents are same XOR will result in zero

- Anonymous February 28, 2010 | Flag Reply