FB面经Prepare: Friends Recommendation

有个getFriend() API, 让你推荐你的朋友的朋友做你的朋友，当然这个新朋友不能是你原来的老朋友

 1 package fb;
 2 
 3 import java.util.*;
 4 
 5 public class ReferFriends {
 6     public List<String> recommendation(String name) {
 7         List<String> res = new ArrayList<String>();
 8         if (name==null || name.length()==0) return res;
 9         
10         List<String> friends = getFriends(name);
11         HashSet<String> set = new HashSet<String>();
12         for (String friend : friends) {
13             set.add(friend);
14         }
15         
16         HashMap<String, Integer> map = new HashMap<String, Integer>();
17         ArrayList<String>[] list = new ArrayList[friends.size()+1];
18         
19         for (String friend : friends) {
20             List<String> ffriends = getFriends(friend);
21             for (String each : ffriends) {
22                 if (!set.contains(each) && !each.equals(name)) {
23                     //map.put(each, map.getOrDefault(each, 0) + 1);
24                     if (map.containsKey(each))
25                         map.put(each, map.get(each)+1);
26                     else map.put(each, 1);
27                 } 
28             }
29         }
30         
31         for (String each : map.keySet()) {
32             int count = map.get(each);
33             if (list[count] == null) list[count] = new ArrayList<String>();
34             list[count].add(each);
35         }
36         
37         for (int k=list.length-1; k>=0; k--) {
38             if (list[k] != null) 
39                 res.addAll(list[k]);
40         }
41         return res;
42         
43     }
44     
45     public List<String> getFriends(String name) {
46         HashMap<String, List<String>> map = new HashMap<String, List<String>>();
47         map.put("Lily", new ArrayList<String>());
48         map.put("Lucy", new ArrayList<String>());
49         map.put("Hanmeimei", new ArrayList<String>());
50         map.put("Jim", new ArrayList<String>());
51         map.put("Lilei", new ArrayList<String>());
52         map.put("Poly", new ArrayList<String>());
53         map.get("Lily").add("Lilei");
54         map.get("Lily").add("Poly");
55         map.get("Lily").add("Hanmeimei");
56         map.get("Lily").add("Jim");
57         map.get("Lucy").add("Lilei");
58         map.get("Lucy").add("Poly");
59         map.get("Lucy").add("Hanmeimei");
60         map.get("Lucy").add("Lily");
61         map.get("Lilei").add("Jim");
62         map.get("Lilei").add("Lucy");
63         map.get("Lilei").add("UncleWang");
64         map.get("Lilei").add("Hanmeimei");
65         map.get("Lilei").add("Lily");
66         map.get("Jim").add("Lily");
67         map.get("Jim").add("Lucy");
68         map.get("Jim").add("Lilei");
69         map.get("Poly").add("Jim");
70         map.get("Poly").add("Lilei");
71         return map.get(name);
72     }
73 
74     /**
75      * @param args
76      */
77     public static void main(String[] args) {
78         // TODO Auto-generated method stub
79         ReferFriends sol = new ReferFriends();
80         //List<String> res = sol.recommendation("Poly");
81         List<String> res = sol.recommendation("Jim");
82         for (String each : res) {
83             System.out.println(each);
84         }
85     }
86 
87 }