一亩三分地论坛

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

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

Facebook 电面

[复制链接] |试试Instant~ |关注本帖
huai10 发表于 2016-9-7 14:12:34 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
楼主内推后一个星期收到电面通知, 今天刚面完,是个白人小哥,一上来也不废话,告诉我今天要做些题

第一题2sum, follow-up 就是3sum
第二题就是找两个array 里面相同的数字, follow-up就是给你一个user_id 和API 接口 get_friend(int id),
让你找出所有user id 是你的朋友的朋友但不是你的朋友,然后根据mutual friends的数量排序,
最后5分钟扯了下为什么要来facebook以及提问

最后求Onsite


补充内容 (2016-9-9 04:41):
今天早上通知onsite

本帖被以下淘专辑推荐:

此用户无名 发表于 2016-9-7 15:18:29 | 显示全部楼层
fb今年居然招new grad了?
回复 支持 反对

使用道具 举报

 楼主| huai10 发表于 2016-9-7 15:32:29 | 显示全部楼层
此用户无名 发表于 2016-9-7 15:18
fb今年居然招new grad了?

额,根据我的情况来看应该还是招的
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2016-9-7 22:20:54 | 显示全部楼层
楼主第二题followup怎么做的啊?
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-9-7 23:55:39 | 显示全部楼层
想了下第二题。

用 set1 代表给定 user 的 one degree 好友; set2 代表给定 user 的 two degree 好友,考虑到好友结构可能是有环无向图,需要确保 set1 和 set2 的交集是空集,这一步可以通过类似 bfs 的思路做。

set2 里的每一个元素都是最终输出 list 的结果,判断 mutual friend 个数的过程可以靠找到里面每一个 user 的 friend 的集合 setCandidate,和 set2 求交集,交集的 cardinality 就是 mutual friend 的数量,按照这个排序就行了~
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-9-18 06:24:18 | 显示全部楼层
mnmunknown 发表于 2016-9-7 23:55
想了下第二题。

用 set1 代表给定 user 的 one degree 好友; set2 代表给定 user 的 two degree 好友, ...

贴个代码,总觉得写的很麻烦,大神看看,该怎么改?
  1. class Solution {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2. public:
  3.   vector<int> friendList(int uid) {
  4.   unordered_set<int> set;
  5.   unordered_map<int, int> dict;
  6.   for (int id : get_friend(uid)) {
  7.     set.insert(id);
  8.   }
  9.   for (auto it = set.begin(); it != set.end(); it++) {
  10.       for (int id : get_friend(*it)) {
  11.         if (id != uid) {
  12.           dict[id]++;
  13.         }
  14.       }
  15.   }
  16.   vector<pair<int, int>> lists;
  17.   for (auto it = dict.begin(); it != dict.end(); it++) {
  18.     lists.push_back(make_pair(it.second, it.first));
  19.   }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.   sort(res.begin(), res.end(), [](pair<int, int> p1, p2){
  21.     return p1.first > p2.second;
  22.   });
  23.   vector<int> res;
  24.   for (auto p:lists) {. from: 1point3acres.com/bbs
  25.     res.push_back(p.second);
  26.   }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.   return res;
  28. }
  29. };
复制代码
. from: 1point3acres.com/bbs
补充内容 (2016-9-18 06:24):. 鍥磋鎴戜滑@1point 3 acres
21 行笔误。 p1.first > p2.first;
回复 支持 反对

使用道具 举报

处川 发表于 2016-9-20 02:37:50 | 显示全部楼层
mnmunknown 发表于 2016-9-7 23:55
想了下第二题。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

用 set1 代表给定 user 的 one degree 好友; set2 代表给定 user 的 two degree 好友, ...

setCandidate 是和set1求交集吧
回复 支持 反对

使用道具 举报

处川 发表于 2016-9-20 02:37:58 | 显示全部楼层
mnmunknown 发表于 2016-9-7 23:55
想了下第二题。
. From 1point 3acres bbs
用 set1 代表给定 user 的 one degree 好友; set2 代表给定 user 的 two degree 好友, ...

setCandidate 是和set1求交集吧
回复 支持 反对

使用道具 举报

meanderer 发表于 2016-9-23 12:50:22 | 显示全部楼层
hello2pig 发表于 2016-9-18 06:24
-google 1point3acres贴个代码,总觉得写的很麻烦,大神看看,该怎么改?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-9-18 06:24):

第11行,是不是还应该判断 id 是否在 set 中,以排除 first degree friends?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 03:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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