fb电面疑问，最优要达到什么程度

最近看fb面经看到有人因为 deep copy linked list with random pointer因为没有写出 O(1)空间复杂度的算法被挂了，所以有点疑惑fb所有面试都需要写道最优吗，举几个例子，比如幺幺斯 拉平二叉树需要写morris traverse的 O(1) space算法吗，以及伞久酒这种需要写并查算法吗，找第k大元素的题需要写quickselect吗，脸家电面毕竟一道题就20min如果不幸遇到新题完全没信心写出这种最优算法

面试遇到过 deep copy linked list with random pointer 这个问题，说完了基础的 O(n) 空间复杂度的方法之后被面试官要求要 O(1) 的。所以如果面试想不出 O(1) 的我觉得也没啥问题，要 hint 就好。

morris 遍历如果考了可以直接向 hr 举报面试官。这东西除了能让面试官装逼之外没有任何意义，并且大部分面试官对 morris 遍历其实是一知半解的。知乎最高赞的一篇 morris 遍历的科普文章就满是漏洞，那篇文章的作者甚至不知道 morris 遍历的可能使用场景。

并查集目前只看到 google 考过，这个知识点一直都是 hard 了，如果时间不够可以不管。很多 union find 的题可以用 bfs/dfs 解决，并且大部分面试官是不知道并查集时间复杂度的。

quickselect 非常不建议在面试中写。fb 高频题「求到原点最近的 k 个点」直接用 heap 做不会有任何问题。quickselect 的问题在于它有非常多不同的写法，你的写法很可能和面试官掌握的写法是不一致的，这会导致在 communication 方面（特别是跑 testcase 这一步）没有任何优势，得不偿失。

这种都无解。。。因素太多了，很多时候都不是自己认为的原因挂，而大家发帖又不可能啥信息都暴露，就一小段太难判断了。

而且相信 lz 不是那种人，但很多人都是碍于面子，表现得不好的地方根本不说或者粉饰，无解。深呼吸继续面吧，每年大厂，尤其脸家都有空位出来，真想去这一次失利没啥

我是国人面试的，只答错一个space complexity就挂了... fb是找工作季唯一一个挂了的电面

蹲一个回答..

很想知道大家的经历和看法。

隔壁的帖子的feedback不是说system design没答好吗，完全没提coding部分的问题。 coding部分是lz自己觉得挂了，实际上看并不是lz主观想的那样。
fb一直都有最优解的说法，能想到最优解肯定是最高要求，尽量呗。

这个问题其实跟你面试的时间点也很有关系。之前看见过一篇fb员工当interviewer的心得，说是fb为了招工上的diversity，对于每个大学都有一定的比例，当你是某个diversity group最后那一批里才开始面试的人，可能就要求高一些吧？不然的话，其实interviewer期待一个更好的复杂度会直接问你follow-up，没问的话说明ta未必期待一个最佳答案。

你再看看那个帖子楼主的补充， 他挂的原因不只没做出O(1) , System Design 没达到要求 BQ 有 red flag, 就算他做出O(1)也不见得能过

小厂DP
颜值高的O(N^N)都行
看不对眼的O(1)都会被挑刺

个人觉得，你说的这几个里边， o(1) copy 和quickselect是基础。  morris traverse， fb不需要。

记得很多公司都是time, space complexity答错是直接拒，尤其是基础数据结构。


“如果不幸遇到新题” 面fb， 你如果把leetcode tag下边fb所有的600题刷了和地里fb三个月内的面经，这个遇到完全新题概率，非常非常小。