Interview Question for Engineer at Yahoo:

Naive approach would be to use a simple nested loop to iterate over the two lists one inside another. This would take O(n^2) runtime, which is not too good.

A better approach would be to use a separate hash map data structure and iterate the two lists separately like the following:

                final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        final int s1 = a1.length;
        for(int i = 0; i < s1; i++) map.put(a1[i], a1[i]);
        final int s2 = a2.length;
        for(int i = 0; i < s2; i++) {
            final int v = a2[i];
            if(map.containsKey(v)) return v;
        }
        throw new RuntimeException("No common value found.");

The above is just to show the algorithm, replace integer with node objects. This will allow runtime of O(n) time assuming the values hash key is well spread. but of course, you will end up with O(n) memory consumption.