CareerCup

nitingupta180's answer is close, but doesn't handle the scenario where there are duplicates. This answer is O(n) time complexity. The additional step required is to decrement the values in the hash table until they hit zero while checking the elements for existence (from the second array).

Here is the source for the complete answer as well as a test scenario:

public class Main {
	public static ArrayList<Integer> findIntersection(ArrayList<Integer> s1, ArrayList<Integer> s2) {
	    Hashtable<Integer, Integer> hashTable = new Hashtable<Integer, Integer>();
	    ArrayList<Integer> intersection = new ArrayList<Integer>();
	    for(int i = 0; i < s1.size(); i++) {
	    	if(s1.get(i) != null) {
		        if(hashTable.get(s1.get(i)) != null) {
		            hashTable.put(s1.get(i), hashTable.get(s1.get(i)) + 1);
		        } else {
		            hashTable.put(s1.get(i), 1);
		        }
	    	}
	    }
	    
	    for(int i = 0; i < s2.size(); i++) {
	    	int s2Val = s2.get(i);
	    	int value;
	        if(hashTable.get(s2Val) != null) {
	        	value = hashTable.get(s2Val);
	        } else {
	        	continue;
	        }
	        
		    if(hashTable.get(s2Val)!= 0) {
		        hashTable.put(s2Val, value - 1); 
		        intersection.add(s2Val);
		    }
	    }
    
	    return intersection;
	}
	
	public static void main(String[] args) {
		//Test list and tree
		ArrayList<Integer> a1 = new ArrayList<Integer>();
		a1.add(1);
		a1.add(1);
		a1.add(1);
		a1.add(4);
		
		ArrayList<Integer> a2 = new ArrayList<Integer>();
		a2.add(2);
		a2.add(2);
		a2.add(2);
		a2.add(1);
		a2.add(4);
		
		ArrayList<Integer> a3 = findIntersection(a1, a2);
		System.out.println(a3.toString());
	}

first, I think you should sort these two list in max(O(nlogn), O(mlogm)) time, then traverse two lists to check their common data and store them in a new array or list in O(m+n) time. so the time complexity is max(O(nlogn), O(mlogm)). later I will give my codes.

traverse the first list and get the lenght. Traverse the 2nd and get the length.

Get the difference len1- len2. On the longest list travel len1-len2 distance from start. Now start tarversing both the lists node by node. you will find the intersection.

Someone asked about the theory of hash tables. This is what I could look up on youTube, seems a good one.

www(dot)youtube(dot)com/watch?v=DF3iUIL7MN8

void intersection(vector<int> list1, vector<int> list2) {

	map<int, int> hashTable;
	map<int, int>::iterator it;
	for (int i=0; i<list1.size(); i++) {
		it = hashTable.find(list1[i]);
		if (it == hashTable.end()) hashTable.insert(pair<int, int>(list1[i], 1));
		else it->second++;
}
	for (int i=0; i<list2.size(); i++) {
	it = hashTable.find(list2[i]);
	if (it != hashTable.end() && it->second != 0) {
		it->second--;
		std::cout<<list2[i]<<endl;
}
}
}

1. If we want to save time, we could use hashtable to store one list, and traverse the other list;
2. If we want to use constant space, we could sort the shorter list, and do binary search for each element in the other (longer) list.

Node getIntersection(Node first, Node second) {
    HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    Node result = first;
    Node cur = null;

    while (first != null) {
        cur = first;

        int num = first.data;
        if (hm.contains(num))
            hm.put(num, hm.get(num)+1);
        else 
            hm.put(num, 1);
        first = first.next;
    }

    while(second != null) {
        int num = second.data;
        if (hm.contains(num)) {
            hm.put(num, hm.get(num)-1);
        }
        else {
            hm.put(num, -1);
        }
        if (hm.get(num) < 0) {
            cur.next = second;
            cur = second;
        }
        second = second.next;
    }

    return result;
}

What if you create 1 interval tree for the first list that has n intergers --> O(log n)
Each interval is a single point, so, it's actually a balanced tree.

Query (search in tree) all m elements of the second list --> O(m * log n)

I think here if u use bit operations , it will be faster than hash. if you know the max number in the list, we can use set and test methods. The operation will be way faster than hash and be O(n + m).

What say?