FB 伦敦 2021.3月 Onsite过经（内有超详细过程，跪求米）

General software engineer interview - 第二轮Onsite面（video） - 通过

一天内4个面试：
1. Coding 45min
2. Coding 45min
3. Behavioral 45min
4. system design 45min

------------------

第一轮：Coding

照例两道题，每道题20min。


第一题：kth largest num
Input: a list of integer
Output: the kth largest of this list
        
Example:
  Arr: [5, 3, 9, 1]
  K = 0, return 9 (the 0th largest)
  K = 1, return 5 (the 1th largest)
  K = 3, return 1 (the 3th largest)
        
先是问了关于输入合法性的问题：
  a. K 有可能大于n
  b. Arr 有可能为空
        
我一开始的想法是按照 kth smallest 来做，把 kth largest 转换为 (n-k)th smallest。
然后说用小根堆，把整个array push进去，接着再连续pop (n-k)次，就能得到 (n-k)th smallest 了。

面试官：这是可行的，那这个堆是不是要把所有item都放进去？有没有办法不把整个list放进去？
我：可以只放k个item进去。。（这时我有点卡壳了，只记得是可以的，但没想明白怎么做。）

然后面试官提示我说：我们先focus在 kth largest，先别转换成 kth smallest，let's leave it later（万万没想到这一句也是个hint啊！用于解决follow up问题！而且估计面试官自己也没注意到他在这里泄露了hint了哈哈）。虽然逻辑上他们是一样的，但是实现细节上有些不同。
然后多亏了这个hint，我也想明白了：直接用min heap，然后先放k个items进去heap，接着继续iterate后面的nums，如果新的num不大于当前的heap root，那么就不放进去。这样能保证整个min heap维护了最大的k个。这样最后的heap root就是kth largest了。

算法讨论完毕，开始写code。

循例分析算法复杂度：【主动去详细分析复杂度能加分！】
  a. 空间：开了一个size 为k的 heap，所以是 O(k)
  b. 时间：for loop 是 O(length of array)，里面的 heappush和heappop都是O(logk) 复杂度，所以总共是 O(len(arr) * logk)

注意：比起直接说O(n)，改为说O(length of the arr)更好，因为这样更精准。如果有别的题目是O(2n)，比起直接说O(n)，最好先说是O(2*len(arr))，解释为什么，再接着说这样是O(len(arr))。
而且在解释的过程中自己思路也会更清晰，就更加不容易答错了。
        

Follow up:
So we know in the worse case, e.g. K is (n-1), the space co

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

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

pi，写了 readNewFeed(…) -> … 这个接口。
然后开始画图做设计。
画完service后开始画db tables，然后写有哪些fields，并且分析说用哪种数据库。

后面还讲到了怎么处理hot data，怎么做notification，怎么做error handling。
也聊到了在Internet受限的地方，要如何改进service。


【面试结果】面试官人很好，题目也是很经典的题目。问的问题我都能答上，我也有主动说一些内容，所以整体感觉还不错。


【总结】SD主要就是要言之有理，能分析利弊，知道怎么做tradeoff。

------------------

最后这个onsite是过了，fb别的不说，速度还真的很快。狗家比fb早面完，结果fb却是先发offer的，给了E5。

不过跟我接触的fb recruiter真的人不咋地，刚给面试结果说通过的时候，我要详细的每一轮的feedback，他不给，说只要过了就好。我解释我要feedback的原因，但他还是不肯给。
接着谈offer的时候，各种PUA我，踩我现公司（我现公司在pre ipo中，被这个recruiter嫌弃得体无完肤），还踩谷歌，真的让我觉得这人素质很低，也很不专业。
不过为了谈个好价格，我还是要心里mmp，脸上笑嘻嘻。


扯远了，总的来说，面试这一块：
* 积极沟通！！
* Think out loud！！
* 不管最后面试结果如何，一定要跟recruiter拿详细的面试反馈！！（方便查缺补漏！）- 遇到不肯给的recruiters那也是没办法 ˉ\_(ツ)_/ˉ

我把面试过程尽量详细地分享出来，是想给大家知道，其实要通过面试真的不用说一上来就给出完美答案，重要的还是沟通过程，通过面试官的提示得到结果写出代码，也是可以通过面试的。

coronaking2020 发表于 2021-4-17 03:13
第一轮第一题quick select O(n)解法没提一下？

这个我当时没有提，因为quick select的最坏情况的复杂度是O(n^2)，就是每次都运气不好挑到个坏pivot。

而且我现在发现了规律，如果面试官他自己的答案是quick select的话，他会想方设法给你提示让你往哪个方向去。而我遇到的这个面试官，沟通的时候能感觉得出来，他是想方设法让我往heap上面去。😅

请叫我热情老八 发表于 2021-4-18 04:15
已加米~想请问楼主，SD轮是怎么准备的？

我想哭，刚给你回复了一大堆，结果点了提交后，被删了。。。。我完全不知道为什么被删了。。。TAT

资料的话，可以去油管搜SystemDesignInterview这个channel，目前有6个视频。讲得很好！

另外，SD面试可以注意一下这几点：
1. 一定要先问问题，当做一个你要做的项目，要先问清楚需求。
2. 先讲大框架，然后引导到你熟悉的那个部分。
3. 一定要think out loud！不需要想清楚了再说，边想边说，如果说着说着发现问题，那就说你发现了问题，为什么有这个问题。这样可以体现你发现问题的能力，也能体现你是有考虑周全的，是加分项的。
4. 找到bottleneck，然后聊解决方案。
5. 聊tradeoff的时候，主动提优缺点是什么，还有对应的改进方法。

丶擦哥 发表于 2021-6-14 15:24
感觉楼主的面试官也都很nice，并且楼主能掌控整个面试让面试官为你所用，很赞！

还想再问一下系统设计， ...

关于掌控面试过程这一块，一开始打招呼的时候真的不要羞涩不要内敛，要多笑笑，让你自己也让面试官都放松一下，我是哪怕遇到不怎么会有表情的面试官，我都逼着自己当做没看见，然后全程微笑，毕竟伸手不打笑脸人嘛，他们心情愉快了，feedback也不会太糟糕。

系统设计还是要准备的，遇到的题目可能会不一样，但来来去去都是一样的几点：core function，db，monitoring，testing，security等等（我另一个谈系统设计面试的帖子里有提到具体有哪些要点）。你可以提前先把能聊的点列出来，面试的时候肯定没法全部都cover到，但是当你说完一部分，面试官也没有提问题的时候，那你可以按照列出来的要点继续说下一部分。

“网络不好的时候怎么办”，这个其实不是我自己提，是面试官问的。所以不用担心自己没想到哦。不同面试官侧重点不一样。你不用担心“我没说完所有的”，因为系统设计面试的时间肯定没法说完所有的。你只要在面试时间内「有条有理地说、好好回答面试官的问题」就够了。面试官也知道时间肯定是不够的。

至于发现问题后怎么进行下去，不用担心哦，发现问题也是加分项的，哪怕你没有答案，你可以详细分析一下这里有个问题，为什么它会是个问题（会带来什么不好的地方）。然后如果有思路就说思路，如果没思路你就直接说“但是我还没有什么思路来解决它”。就当做是跟同事在讨论问题就好了~
放心，到这里面试官肯定会给你提示了，而且不会扣你分的，因为你已经分析了“为什么它会是个问题”。如果面试官还没给提示（新手面试官是有可能的），那么你可以直接说“你能给我点提示吗”。
拿提示不一定会扣分，比如你能根据一个提示回答上来，那么完全OK；比如你要多几个提示才能答上来，那也可以过的，不过可能会weak hire，看面试官心情。所以营造好的面试氛围很重要啊，让他感受到跟你一起共事是很愉悦的事情，那很多不太圆满的地方他都可以放过你的。

第一轮第一题quick select O(n)解法没提一下？

非常感谢提供follow up 问题，太珍贵了

感谢lz分享！

已加米~想请问楼主，SD轮是怎么准备的？

请叫我热情老八 发表于 2021-4-18 04:15
已加米~想请问楼主，SD轮是怎么准备的？

在YouTube有个channel叫做SystemDesignInterview，那个讲得特别好，目前有6个视频了。（回复里发链接被删回复了，所以我就不贴链接了）

另外，SD面试有几点注意的：
1. 一定要先问清楚，把题目当做一个你要做的project，先了解清楚需求。
2. 先说大框架，然后引导到你熟悉的那个部分进行细说。
3. Think out loud！不用想清楚了再说出来，一定要边想边说，然后如果说着说着发现问题，那就解释原因，说为什么这样有问题。这样能体现你发现问题的能力，也能体现你对这方面的了解。
4. 找到bottleneck，聊解决方案。
5. 聊tradeoff的时候主动说清楚优缺点，和对应的改进方法。

赞，请问楼主，是在美国申请的FB 伦敦职位么？

害群之蚂蚁 发表于 2021-4-18 12:19
赞，请问楼主，是在美国申请的FB 伦敦职位么？

不是，我现在就在伦敦的。因为这边实在找不到欧洲英国的求职板块，所以只能发到北美求职了。

不过我觉得如果有兴趣来伦敦的话，可以申请一下伦敦的职位。
最近伦敦这里的fb要扩招，开了很多位置。而且本来fb也不介意给面试者relocate的。