Interview Question for Software Development Engineer at Amazon.com:

Initially I suggested sorting the sets and and than iterating the sets to find matches O(nlogn) and later we discussed solving the problem using hash tables O(n). We also discussed performance of the solutions and the possible large cost of hash function.

public void setIntersection(LinkList list1, LinkList list2) {
        LinkList list4 = new LinkList();
        Node a = list1.head;
        Node b = list2.head;
        while (a != null && b != null) {
            if (a.value < b.value) {
                a = a.next;
            } else if (a.value > b.value) {
                b = b.next;
            } else if (a.value == b.value){
                list4.insert(a.value);
                a = a.next;
                b = b.next;
            }
        }
        list4.printList();
    }
}

Assuming we are using lists and the lists are already sorted, we can iterate through the lists and compare values and whenever there is a match, we can store the values in a new list.

public void setIntersection(LinkList list1, LinkList list2) {
        LinkList list4 = new LinkList();
        Node a = list1.head;
        Node b = list2.head;
        while (a != null && b != null) {
            if (a.value < b.value) {
                a = a.next;
            } else if (a.value > b.value) {
                b = b.next;
            } else if (a.value == b.value){
                list4.insert(a.value);
                a = a.next;
                b = b.next;
            }
        }
        list4.printList();
    }
}