Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Interview challenge: Find the different elements in two arrays

Tags:

algorithm

  • Stage 1: Given two arrays, say A[] and B[], how could you find out if elements of B is in A?

  • Stage 2: What about the size of A[] is 10000000000000... and B[] is much smaller than this?

  • Stage 3: What about the size of B[] is also 10000000000.....?

My answer is as follows:

  • Stage 1:

    1. double for loop - O(N^2);
    2. sort A[], then binary search - O(NlgN)
  • Stage 2: using bit set, since the integer is 32bits....

  • Stage 3: ..

Do you have any good ideas?

like image 362
deepsky Avatar asked Oct 13 '11 15:10

deepsky


1 Answers

hash all elements in A [iterate the array and insert the elements into a hash-set], then iterate B, and check for each element if it is in B or not. you can get average run time of O(|A|+|B|).

You cannot get sub-linear complexity, so this solution is optimal for average case analyzis, however, since hashing is not O(1) worst case, you might get bad worst-case performance.

EDIT:

If you don't have enough space to store a hash set of elements in B, you might want to concider a probabilistic solution using bloom filters. The problem: there might be some false positives [but never false negative]. Accuracy of being correct increases as you allocate more space for the bloom filter.

The other solution is as you said, sort, which will be O(nlogn) time, and then use binary search for all elements in B on the sorted array.

For 3rd stage, you get same complexity: O(nlogn) with the same solution, it will take approximately double time then stage 2, but still O(nlogn)

EDIT2:
Note that instead of using a regular hash, sometimes you can use a trie [depands on your elements type], for example: for ints, store the number as it was a string, each digit will be like a character. with this solution, you get O(|B|*num_digits+|A|*num_digits) solution, where num_digits is the number of digits in your numbers [if they are ints]. Assuming num_digits is bounded with a finite size, you get O(|A|+|B|) worst case.

like image 193
amit Avatar answered Sep 19 '22 15:09

amit