CareerCup

Sorting is O(nlogn) which is not good.
hash the first set. Then hash the second set and check if it already exist. If yes, then put the element in the intersection array.

If no duplicates then hashing is a good way to do !
but if there's duplicate then it will have some collision, then hashing will no longer be the best. I think consider this case, sort the small sets and do the binary search will be the best.

Sort the two set.... O(nlogn)
Compare from starting element:
If set one element is less than set two, go to next element in set one and vice versa.
If the two are equal, store in another array and go to next elements in both the sets.
This will take O(n) time. So the total complexity is still better than O(n2).

By set definition each set cannot have duplicates. Merge them together, sort, look for duplicates. The set of duplicates would be the intersection.

Suppose we have, s1 = {a,b,c,d}, and s2={c,d,e,f}
Populate s1 in a hash table. e.g s1h, and check s2 elements in s1h, the elements in s2 that exists in s1h will be the intersection.

consider 2 sets of unequal sizes, A and B.

sort them in ascending order
assumed that since it is a set, there are no duplicates

num of elems in A = size(A)
num of elems in B = size(B)
create a 3rd array C with size = min(size(A), size(B)) // intersection cannot be greater than smallest array

while(int i < size(A)) //assuming size(A) < size(B)
while(int j < size(B))
if(A[i] < B[j])
i++
else if A[i] > B[j]
j++
else
copy A[i] into C
i++
j++

terminate when smaller array goes out of bounds, so dont need to check for all elements

this is just like the join in database, without index, hashing is definitely the best solution.

Set<Long> a = new HashSet<Long>();
Set<Long> b = new HashSet<Long>();
Set<Long> intersection = new HashSet<Long>();

a.add(1L);
a.add(2L);
a.add(3L);
a.add(4L);

b.add(5L);
b.add(6L);
b.add(2L);
b.add(3L);

for(Long x : b){
if (!a.add(x)) {
intersection.add(x);
}
}

for(Long x : intersection){
System.out.print(x +" , ");
}