Facebook 二面

我是前天的面试，面试官一上来直接出题，然后说可能会出1到两题，到时看时间。
题目：

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

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

流程：
我之前就做过这道题，但是当时可能因为紧张忘记自己之前怎么做的，所以我就从当时想到的几种tree traversal中选了自己最有把握的。现在回想起来庆幸当时重新思考应该怎么做，而不是死记自己以前的做法。
在解释我的做法的过程中，面试官指出了我的错误，这样让我省下了之后写错code的时间。所以在写code之前交流想法很重要，nice的面试官可能会提早纠正你。
写完之后我主动走了test case，这样方便自己检查code。
快结束想着挺顺利，心里还挺开心，结果被问空间复杂度，随口说了第一感觉的答案，但是用词不确定，面试官紧接就问理由，然后我才开始认真分析，最终得到一个他还算肯定的答案。如果再让我答一次，我一定不会随口给一个答案，应该给面试官分析过后再得出答案。而且我过于依赖他的口气来猜正确答案，下次一定要自己先独立思考，把自己的思路理清，先不要管对错， 完整地表述出来，体现自己drive interview和独立思考的能力，recruiter一直说他们想要这样积极主动的人。
我最后只完成了一题，然后问他要不要再出一道，他说时间到了，题目就足够了。



反馈：
虽然被邀请onsite, 但是果然最后时间复杂度分析欠佳，在准备过程真的要多多思考啊，而且best case, worst case和average complexity都要考虑，如果能用formula表示，就要想formula是什么。onsite要考的system design正是我现在工作欠缺的，感觉很没有底气，希望能找到地里的题目好好练习！


补充内容 (2018-5-16 07:21):
如果你喜欢这个分享的话，请在下面“评分”给我加一点米，这样是不会扣你自己的分的。接下来要准备onsite, 需要大米才能看到一些材料，提前谢谢你了！

// 结果被问空间复杂度,问的是时间复杂度吧

cexq 发表于 2018-4-23 13:24
// 结果被问空间复杂度,问的是时间复杂度吧

问空间复杂度，所以才意想不到啊

樓主空間複雜度應該就是Tree裏面node的個數吧

多谢楼主的分享

补充内容：如果你正在看我的帖子而且还比较喜欢的，请在下面“评分”给我加一点米，这样是不会扣你自己的分的。接下来要准备onsite, 需要大米才能看到一些材料，提前谢谢你了！

空间复杂度和时间复杂度都是O(N)吧