May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1846|回复: 18
收起左侧

Google 一道面经题

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

本帖被以下淘专辑推荐:

alen231x 发表于 2016-2-4 10:49:22 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
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){. 1point3acres.com/bbs
   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]++;
         }
   }
}
第三步:. more info on 1point3acres.com
int maxFrindsNum = INT_MIN, res;
for(auto m : mp){
     if(m.second > maxFriendsNum) {
            res = m.first;
            maxFriendsNum = m.second;. more info on 1point3acres.com
     }.1point3acres缃
}
return res;. visit 1point3acres.com for more.

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

使用道具 举报

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

补充内容 (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;-google 1point3acres
if(p.second == target) mp[p.first] = 1;
}
第二步:
for(auto p : pairs){
   if(mp.count(p.first) && mp.count(p.second)) {
         mp[p.first]++;. visit 1point3acres.com for more.
         mp[p.second]++;
         }
   }. Waral 鍗氬鏈夋洿澶氭枃绔,
}
第三步:
int maxFrindsNum = INT_MIN, res;
for(auto m : mp){
     if(m.second > maxFriendsNum) {
            res = m.first;
            maxFriendsNum = m.second;
     }
}
return res;. 鍥磋鎴戜滑@1point 3 acres
时空复杂度:O(N)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

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

使用道具 举报

alen231x 发表于 2016-2-3 13:23:04 | 显示全部楼层
javaprogrammer 发表于 2016-2-3 13:05. From 1point 3acres bbs
没太看懂这个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
请问第二部是啥意思?

第二步是找target之间的好友之间的共同好友数量,第二步里新添加的pair对值中的两个数必须之前在mp中. Waral 鍗氬鏈夋洿澶氭枃绔,
例如【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有最多的公共好友。.1point3acres缃
比如:[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
回复 支持 反对

使用道具 举报

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本身和他的好友
第一步:
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);
}
第二步:. Waral 鍗氬鏈夋洿澶氭枃绔,
建立一个map存储target的第二级好友与自己共同好友数量. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
unordered_map<int, int> mp
for(auto p : pairs){
   if(set.count(p.first) || set.count(p.second)) {
. from: 1point3acres.com/bbs         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]++;.1point3acres缃
   }
}. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第三步:
int maxFrindsNum = INT_MIN, res;. 1point3acres.com/bbs
for(auto m : mp){
     if(m.second > maxFriendsNum) {
            res = m.first;. Waral 鍗氬鏈夋洿澶氭枃绔,
            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 {. 1point 3acres 璁哄潧

  2.         class People {
  3.                 String name;
  4.                 HashSet<People> friends;
  5.         }
  6. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.         class Ele {
  8.                 int count;
  9.                 People people;
  10. . 鍥磋鎴戜滑@1point 3 acres
  11.                 public Ele(int c, People n) {
    . 鍥磋鎴戜滑@1point 3 acres
  12.                         count = c;
  13.                         people = n;
  14.                 }
  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)) {. 1point 3acres 璁哄潧
  25.                                         map.put(ele, 1);
  26.                                 } else {
  27.                                         map.put(ele, map.get(ele) + 1);
  28.                                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.                         }
  30.                 }

  31.                 PriorityQueue<Ele> pq = new PriorityQueue<Ele>(new Comparator<Ele>() {
  32.                         public int compare(Ele e1, Ele e2) {
  33.                                 return e2.count - e1.count;
  34.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.                 });
  36.                 while (!pq.isEmpty()) {
  37.                         res.add(pq.poll().people);
  38.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  39.                 return res;
  40.         }
  41. }
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 18:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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