Problem 1: You are given two arrays A and B containing elements from a set U. You want to partition the union of A and B in two sets D and S, where S contains the elements that appear only in A or only in B, and D contains all elements appearing in both A and B. Your algorithm should run in linear time (i.e. O(n) where n = |A| + |B|).

Solution: Hash all the elements of A into a hash table of size n resolving collisions using a linked list. Assuming simple uniform hashing each slot will have an average of O(1) elements. Now hash the elements of B. If an element of B hashed into an empty slot put it in S. If the element hashes into an occupied slot, then check if it appears in the list. If it does not, then you add it to S. If it does appear in the list, that means the element is also in A, therefore you add it to D and remove it from the hash table. At the end all the elements left in the hash table are singles (since they are elements of A that do not appear in B) and can be added to S. The running time is expected O(n) since we hash each element once, and the search takes expected O(1).

note: I attach the solution also but i need the algorithm that match with the solution. the algorithm should be same as the given solution