Sunday, March 22, 2015

Find email which exists in every list

Write a function that will take in email lists and return a new email list that contains only the email addresses that existed in all lists 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
1: foo@amazon.combar@amazon.com. 1point 3acres 璁哄潧
2: bar@amazon.combar@amazon.com. visit 1point3acres.com for more.
o: bar@amazon.com

Solution:
Using two hashset, here are set1 and set2.
1. Store every email in list1 into set1;
2. Start from list2, if email is existed in set1, then add it into set2. After finishing traverse this list, clear set1, copy every email in set2 into set1, then clear set2. Move on to next list.
3. After traversing every list, set1 contains the email addresses that exist in every list. Just return set1.
Run time complexity is O(m * n), m is the number of lists, n is the number of email per list. Space complexity is O(n), n is number of email addresses in list1.
public static ArrayList existInAll(ArrayList> lists) throws Exception{
		if(lists == null) {
			return null;
		}
		
		HashSet set1 = new HashSet();
		HashSet set2 = new HashSet();
		
		for(int i = 0; i < lists.get(0).size(); i++) {
			String str = lists.get(0).get(i);
			set1.add(str);
		}
		
		for(int i = 1; i < lists.size(); i++) {
			for(int j = 0; j < lists.get(i).size(); j++) {
				String cur = lists.get(i).get(j);
				if(set1.contains(cur)) {
					set2.add(cur);
				}
			}
			set1.clear();
			Iterator iterator = set2.iterator();
			while(iterator.hasNext()) {
				set1.add((String)iterator.next());
			}
			set2.clear();
		}
		
		Iterator getRes = set1.iterator();
		ArrayList res = new ArrayList();
		while(getRes.hasNext()) {
			res.add((String)getRes.next());
		}
		
		if(res.size() == 0) {
			System.out.println("Can't find any email which exists in every list.");
		}else {
			for(String s : res) {
				System.out.println(s);
			}
		}
		
		return res;
	}

No comments:

Post a Comment