## Sunday, January 24, 2016

### G面经prepare: Friends Recommendation - neverlandly - 博客园

G面经prepare: Friends Recommendation - neverlandly - 博客园
`想想如果你用linkedin或者facebook， 给你一个人和他的朋友关系网，你会怎么给一个人推荐朋友`

``` 5     public char recommend(char tar, char[][] arr) {
6         HashMap<Character, HashSet<Character>> graph = new HashMap<Character, HashSet<Character>>();
7         HashMap<Character, Integer> SndIndegree = new HashMap<Character, Integer>();
8
9
10         //build graph
11         for (char[] edge : arr) {
12             if (!graph.containsKey(edge[0])) graph.put(edge[0], new HashSet<Character>());
13             if (!graph.containsKey(edge[1])) graph.put(edge[1], new HashSet<Character>());
15             if (!SndIndegree.containsKey(edge[0])) SndIndegree.put(edge[0], 0);
16             if (!SndIndegree.containsKey(edge[1])) SndIndegree.put(edge[1], 0);
17         }
18
19         Queue<Character> queue = new LinkedList<Character>();
20         HashSet<Character> visited = new HashSet<Character>();
21         int level = 0;
22         queue.offer(tar);
24         int PNum = 1;
25         int CNum = 0;
26         int maxIndegree = 0;
27         char res = '\0';
28         while (!queue.isEmpty()) {
29             char cur = queue.poll();
30             PNum--;
31             for (Character neigh : graph.get(cur)) {
32                 if (level+1 == 2) {
33                     if (neigh == tar) continue;
34                     int curIndegree = SndIndegree.get(neigh)+1;
35                     if (curIndegree > maxIndegree) res = neigh.charValue();
36                     SndIndegree.put(neigh, curIndegree);
37                 }
38                 else { //not second level
39                     if (!visited.contains(neigh)) {
40                         queue.offer(neigh);
41                         CNum++;
43                     }
44                 }
45             }
46             if (PNum == 0) {
47                 PNum = CNum;
48                 CNum = 0;
49                 level++;
50             }
51         }
52         return res;
53     }
59     public static void main(String[] args) {
60         // TODO Auto-generated method stub
61         Solution sol = new Solution();
62         char res = sol.recommend('A', new char[][]{{'A','B'},{'A','C'},{'B','D'},{'B','E'},{'C','D'},{'B','A'},{'C','A'}});
63         System.out.println(res);
64     }```
Read full article from G面经prepare: Friends Recommendation - neverlandly - 博客园