2016-06-17-亚马逊电面

//You are given two lists. Write a method that checks for duplicate elements in the second list.
// test cases :
// listA: [1,2,3,4]
// listB: [3,6,8.5]
// 
// invalidList: [1,2,3,3]
// hasDupliactes(listA, listB) -> true
//boolean
// list sorted?
// O(lenA * LenB)

// hashset 

// sort A , sort B
// and do binary search 
// O(logn)

// hashset

// set   add List A into set , no duplicate in list A
//  continue add ListB into set , if duplicate one , set will failed.  return false
// O(len A + len B) 


// use two LinkedHashSet 

// Add list A into  set 1  
// Add list B into set 2
// Add element from set2 into set 1
import java.util.*;
import java.util.HashSet;

public class FindDuplicate {
    public static void main(String[] args) {
        Integer[] array1 = { 1, 2, 3, 4};
        Integer[] array2 = {3, 6, 8, 5};
        FindDuplicate finder = new FindDuplicate();
        System.out.println(finder.checkDuplicate(array1, array2));
    }
    
    public boolean checkDuplicate(Integer[] array1, Integer[] array2) {
        Set<Integer> set1 = new HashSet<Integer>(Arrays.asList(array1));
        Set<Integer> set2 = new HashSet<Integer>(Arrays.asList(array2));
        // if set2.size() > set1.size()
        
        for (int element : set2) {
            if (!set1.add(element)) {
                return true;
            }
        }
        return false;
    }
    
    // second solution
    // int pointA // pointer
}