Google 一道面经题

jill_8668 发表于 2016-2-4 04:25
嗯， 您解释清楚了。 但我不确定题目是不是这个意思。 就拿您的例子， 2已经是1的好友了，为啥还要推荐？ ...

LZ的题意是说“推荐一个有最多个公共好友的好友”， 我理解的意思就是推荐已有好友中最多公共好友的那个。
不过如果按照您现在的意思，下面是的改过的方法：
第一步：//set添加所有好友和自身
unordered_set<int> set;
set.insert(target);
for(auto p : pairs){
if(p.first == target) set.insert(p.second);
if(p.second == target) set.insert(p.first);
}
第二步：//统计飞target好友与自己公共好友数量
unordered_map<int, int> mp;
for(auto p : pairs){
   if(set.count(p.first) || set.count(p.second)) {
         if(set.count(p.second) && set.count(p.first) == 0) mp[p.first]++;
         if(set.count(p.first) && set.count(p.second) == 0) mp[p.second]++;
         }
   }
}
第三步：
int maxFrindsNum = INT_MIN, res;
for(auto m : mp){
     if(m.second > maxFriendsNum) {
            res = m.first;
            maxFriendsNum = m.second;
     }
}
return res;

时空复杂度：O（N）

题目的要求是返回所有的friends， 按照popular程度排序（不是返回最popular的那个）

jill_8668 发表于 2016-2-4 04:25
嗯， 您解释清楚了。 但我不确定题目是不是这个意思。 就拿您的例子， 2已经是1的好友了，为啥还要推荐？ ...

按照您理解的意思，我的改进方法是
建立一个set存储target本身和他的好友
第一步：
unordered_set<int> set;
set.insert(target);
for(auto p : pairs){
if(p.first == target) set.insert(p.second);
if(p.second == target) set.insert(p.first);
}
第二步：
建立一个map存储target的第二级好友与自己共同好友数量
unordered_map<int, int> mp
for(auto p : pairs){
   if(set.count(p.first) || set.count(p.second)) {
        if(set.count(p.second) && set.count(p.first) == 0) mp[p.first]++;
        if(set.count(p.first) && set.count(p.second) == 0) mp[p.second]++;
   }
}
第三步：
int maxFrindsNum = INT_MIN, res;
for(auto m : mp){
     if(m.second > maxFriendsNum) {
            res = m.first;
            maxFriendsNum = m.second;
     }
}
return res;
时空复杂度：O(N)

guixi107 发表于 2016-2-4 11:18
题目的要求是返回所有的friends， 按照popular程度排序（不是返回最popular的那个）

参照我的第一解法，从mp中取出来后sort一遍就好了~

你理解错了吧？我怎么觉得是所有朋友的好友中出现频率高的呢？

kittycerry 发表于 2016-3-8 15:08
你理解错了吧？我怎么觉得是所有朋友的好友中出现频率高的呢？

你指的出现频率高是什么？是和target有更多相同好友吗？如果是这样，那就是一个意思啊

我单纯的没看明白你题目的意思。或者你把人家的原帖链接贴一下？谢谢

自己写了个java代码

1. public class FriendsRecommendation {
   
2. 
   
3.         class People {
   
4.                 String name;
   
5.                 HashSet<People> friends;
   
6.         }
   
7. 
   
8.         class Ele {
   
9.                 int count;
   
10.                 People people;
    
11. 
    
12.                 public Ele(int c, People n) {
    
13.                         count = c;
    
14.                         people = n;
    
15.                 }
    
16.         }
    
17. 
    
18.         public List<People> findPotentialFriends(People p) {
    
19.                 List<People> res = new ArrayList<People>();
    
20.                 HashMap<People, Integer> map = new HashMap<People, Integer>();
    
21.                 for (People friend : p.friends) {
    
22.                         for (People ele : friend.friends) {
    
23.                                 if (p.friends.contains(ele)) {
    
24.                                         continue;
    
25.                                 }
    
26.                                 if (!map.containsKey(ele)) {
    
27.                                         map.put(ele, 1);
    
28.                                 } else {
    
29.                                         map.put(ele, map.get(ele) + 1);
    
30.                                 }
    
31.                         }
    
32.                 }
    
33. 
    
34.                 PriorityQueue<Ele> pq = new PriorityQueue<Ele>(new Comparator<Ele>() {
    
35.                         public int compare(Ele e1, Ele e2) {
    
36.                                 return e2.count - e1.count;
    
37.                         }
    
38.                 });
    
39.                 while (!pq.isEmpty()) {
    
40.                         res.add(pq.poll().people);
    
41.                 }
    
42. 
    
43.                 return res;
    
44.         }
    
45. }
    

复制代码

kittycerry 发表于 2016-3-9 05:24
我单纯的没看明白你题目的意思。或者你把人家的原帖链接贴一下？谢谢

我也忘了从哪复制的。可以看下这个http://www.1point3acres.com/bbs/ ... p;page=1#pid2289946