Google 一道面经题

看到面经中一道，推荐一个有最多个公共好友的好友 （BFS

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

数，找出最多的。有没有更好的办法呢？

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）

自己写了个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. }
    

复制代码

如果只是隔着一层的共同好友可能不需要hashset？可不可以对target做一层BFS，对得到的每个点也做一层BFS，用计数器记住每个点出现的次数最多的就是想要的结果？

补充内容 (2016-2-3 06:52):
不知道有没有分析错，空间复杂度是o(n)时间复杂度是o(n)?n是点的个数

假设你这个关系图是是pair对给的，存在vector<pair<int, int>> pairs,  int target是目标点
第一步：
for(auto p : pairs){
if(p.first == target) mp[p.second] = 1;
if(p.second == target) mp[p.first] = 1;
}
第二步：
for(auto p : pairs){
   if(mp.count(p.first) && mp.count(p.second)) {
         mp[p.first]++;
         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)

alen231x 发表于 2016-2-3 08:38
假设你这个关系图是是pair对给的，存在vector pairs,  int target是目标点
第一步：
for(auto p : pairs) ...

没太看懂这个target是什么意思呢。。。

javaprogrammer 发表于 2016-2-3 13:05
没太看懂这个target是什么意思呢。。。

target初始的要被推荐的那个人的ID

alen231x 发表于 2016-2-3 08:38
假设你这个关系图是是pair对给的，存在vector pairs,  int target是目标点
第一步：
for(auto p : pairs) ...

第一步是 找出target的好友 标记为1
请问第二部是啥意思？

jill_8668 发表于 2016-2-3 13:42
第一步是 找出target的好友 标记为1
请问第二部是啥意思？

第二步是找target之间的好友之间的共同好友数量，第二步里新添加的pair对值中的两个数必须之前在mp中
例如【1， 2】， 【2， 3】，【1，3】，【1，4】，【2，4】， 【4， 5】， 【3，5】target是1：
第一步之后
mp[2] = 1， mp[3] = 1, mp[4] = 1
第二步之后：
mp[2] = 3, mp[3] = [2], mp[4] = 2
所以index为2的那个人与1的共同好友最多

C++里map那个count函数的意思就是判断那个key是否在map里出现过，没出现的话返回0

希望我解释清楚了

alen231x 发表于 2016-2-3 14:28
希望我解释清楚了

嗯， 您解释清楚了。 但我不确定题目是不是这个意思。 就拿您的例子， 2已经是1的好友了，为啥还要推荐？

我的理解是，推荐一位，目前不是1的好友， 但和1有最多的公共好友。
比如：［1，2］ ［1，3］ ［1，4］［1，5］［2，6］［3，6］［4，6］［5，6］［3，7］［4，7］

这里6和1拥有4位公共好友， 而7月1只有2位公共好友， 所以应该推荐6