Facebook 电面

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

第一题2sum, follow-up 就是3sum
第二

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

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

/>


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

fb今年居然招new grad了？

此用户无名 发表于 2016-9-7 15:18
fb今年居然招new grad了？

额，根据我的情况来看应该还是招的

楼主第二题followup怎么做的啊？

想了下第二题。

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

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

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) {
    
25.     res.push_back(p.second);
    
26.   }
    
27.   return res;
    
28. }
    
29. };

复制代码

补充内容 (2016-9-18 06:24):
21 行笔误。 p1.first > p2.first;

mnmunknown 发表于 2016-9-7 23:55
想了下第二题。

用 set1 代表给定 user 的 one degree 好友； set2 代表给定 user 的 two degree 好友， ...

setCandidate 是和set1求交集吧

mnmunknown 发表于 2016-9-7 23:55
想了下第二题。

用 set1 代表给定 user 的 one degree 好友； set2 代表给定 user 的 two degree 好友， ...

setCandidate 是和set1求交集吧

hello2pig 发表于 2016-9-18 06:24
贴个代码，总觉得写的很麻烦，大神看看，该怎么改？

补充内容 (2016-9-18 06:24):

第11行，是不是还应该判断 id 是否在 set 中，以排除 first degree friends？