一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1357|回复: 18
收起左侧

Google 一道面经题

[复制链接] |试试Instant~ |关注本帖
bobzhang2004 发表于 2016-2-3 06:30:11 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
看到面经中一道,推荐一个有最多个公共好友的好友 (BFS)。有大神可以说一下解法吗?brute force 应该比较简单,就是找出每个好友,然后用hashset存着好友,然后拿另一个的好友,查看在不在set中,进行计数,找出最多的。有没有更好的办法呢?
. more info on 1point3acres.com

本帖被以下淘专辑推荐:

alen231x 发表于 2016-2-4 10:49:22 | 显示全部楼层
jill_8668 发表于 2016-2-4 04:25
嗯, 您解释清楚了。 但我不确定题目是不是这个意思。 就拿您的例子, 2已经是1的好友了,为啥还要推荐? ...
-google 1point3acres
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) {
.鏈枃鍘熷垱鑷1point3acres璁哄潧            res = m.first;
            maxFriendsNum = m.second;
     }
}
return res;

时空复杂度:O(N)
回复 支持 1 反对 0

使用道具 举报

testgre 发表于 2016-2-3 06:46:22 | 显示全部楼层
如果只是隔着一层的共同好友可能不需要hashset?可不可以对target做一层BFS,对得到的每个点也做一层BFS,用计数器记住每个点出现的次数最多的就是想要的结果?.1point3acres缃

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

使用道具 举报

alen231x 发表于 2016-2-3 08:38:18 | 显示全部楼层
假设你这个关系图是是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)) {-google 1point3acres
         mp[p.first]++;
         mp[p.second]++;
         }
   }
鏉ユ簮涓浜.涓夊垎鍦拌鍧. }
. from: 1point3acres.com/bbs 第三步:. 鍥磋鎴戜滑@1point 3 acres
int maxFrindsNum = INT_MIN, res;. 1point3acres.com/bbs
for(auto m : mp){
     if(m.second > maxFriendsNum) {
            res = m.first;
            maxFriendsNum = m.second;-google 1point3acres
     }
}
return res;
. 1point3acres.com/bbs时空复杂度:O(N)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2016-2-3 13:05:15 | 显示全部楼层
alen231x 发表于 2016-2-3 08:38.1point3acres缃
假设你这个关系图是是pair对给的,存在vector pairs,  int target是目标点
第一步:
for(auto p : pairs) ...

没太看懂这个target是什么意思呢。。。
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-3 13:23:04 | 显示全部楼层
javaprogrammer 发表于 2016-2-3 13:05
没太看懂这个target是什么意思呢。。。

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jill_8668 发表于 2016-2-3 13:42:36 | 显示全部楼层
alen231x 发表于 2016-2-3 08:38
假设你这个关系图是是pair对给的,存在vector pairs,  int target是目标点
第一步:
for(auto p : pairs) ...

第一步是 找出target的好友 标记为1
请问第二部是啥意思?
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-3 14:23:22 | 显示全部楼层
jill_8668 发表于 2016-2-3 13:42
第一步是 找出target的好友 标记为1
请问第二部是啥意思?
. 1point3acres.com/bbs
第二步是找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的共同好友最多
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-3 14:27:46 | 显示全部楼层
C++里map那个count函数的意思就是判断那个key是否在map里出现过,没出现的话返回0
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-3 14:28:06 | 显示全部楼层
希望我解释清楚了
回复 支持 反对

使用道具 举报

jill_8668 发表于 2016-2-4 04:25:38 | 显示全部楼层
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]. 1point 3acres 璁哄潧

这里6和1拥有4位公共好友, 而7月1只有2位公共好友, 所以应该推荐6
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-4 11:18:19 | 显示全部楼层
题目的要求是返回所有的friends, 按照popular程度排序(不是返回最popular的那个)
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-5 08:07:00 | 显示全部楼层
jill_8668 发表于 2016-2-4 04:25
嗯, 您解释清楚了。 但我不确定题目是不是这个意思。 就拿您的例子, 2已经是1的好友了,为啥还要推荐? ...

按照您理解的意思,我的改进方法是
建立一个set存储target本身和他的好友.1point3acres缃
第一步:
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)) {. Waral 鍗氬鏈夋洿澶氭枃绔,
        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){. 1point3acres.com/bbs
     if(m.second > maxFriendsNum) {
            res = m.first;
            maxFriendsNum = m.second;
     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}
return res;
时空复杂度:O(N)
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-5 08:07:59 | 显示全部楼层
guixi107 发表于 2016-2-4 11:18
题目的要求是返回所有的friends, 按照popular程度排序(不是返回最popular的那个)

参照我的第一解法,从mp中取出来后sort一遍就好了~
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-8 15:08:08 | 显示全部楼层
你理解错了吧?我怎么觉得是所有朋友的好友中出现频率高的呢?
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-8 23:10:53 | 显示全部楼层
kittycerry 发表于 2016-3-8 15:08
你理解错了吧?我怎么觉得是所有朋友的好友中出现频率高的呢?

你指的出现频率高是什么?是和target有更多相同好友吗?如果是这样,那就是一个意思啊
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-9 05:24:15 | 显示全部楼层
我单纯的没看明白你题目的意思。或者你把人家的原帖链接贴一下?谢谢
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-9 06:36:54 | 显示全部楼层
自己写了个java代码
  1. public class FriendsRecommendation {
  2. . 1point 3acres 璁哄潧
  3.         class People {. more info on 1point3acres.com
  4.                 String name;
  5.                 HashSet<People> friends;
  6.         }
  7. . more info on 1point3acres.com
  8.         class Ele {
  9.                 int count;
  10.                 People people;

  11.                 public Ele(int c, People n) {
  12.                         count = c;
  13.                         people = n;
  14.                 }. visit 1point3acres.com for more.
  15.         }

  16.         public List<People> findPotentialFriends(People p) {
  17.                 List<People> res = new ArrayList<People>();
  18.                 HashMap<People, Integer> map = new HashMap<People, Integer>();
  19.                 for (People friend : p.friends) {
  20.                         for (People ele : friend.friends) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.                                 if (p.friends.contains(ele)) {
  22.                                         continue;
  23.                                 }
  24.                                 if (!map.containsKey(ele)) {
  25.                                         map.put(ele, 1);
  26.                                 } else {
  27.                                         map.put(ele, map.get(ele) + 1);
  28.                                 }
  29.                         }
  30.                 }
  31. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.                 PriorityQueue<Ele> pq = new PriorityQueue<Ele>(new Comparator<Ele>() {
  33.                         public int compare(Ele e1, Ele e2) {
  34.                                 return e2.count - e1.count;
  35.                         }
  36.                 });
  37.                 while (!pq.isEmpty()) {
  38.                         res.add(pq.poll().people);
  39.                 }. 1point 3acres 璁哄潧
  40. . 1point3acres.com/bbs
  41.                 return res;
  42.         }
  43. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-9 06:38:32 | 显示全部楼层
kittycerry 发表于 2016-3-9 05:24
我单纯的没看明白你题目的意思。或者你把人家的原帖链接贴一下?谢谢

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 22:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表