Google 一道面经题

看到面经中一道，推荐一个有最多个公共好友的好友 （BFS）。有大神可以说一下

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

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

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

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

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

自己写了个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是点的个数

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

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

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
请问第二部是啥意思？

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

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

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

希望我解释清楚了

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

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