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

面试遇到过 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 这一步）没有任何优势，得不偿失。

最优当然关键在最字。
不过为了面试时间，很多时候需要取舍。最优不一定好写，写错了反而得不偿失。

看面试官，一般不需要最优解，能够完美给出最优解肯定最好，给不出就看你解题思路，是否能把思路转成比较高质量的代码，是否能正确分析自己解法的复杂度，是否能自己做测试，沟通如何，是否能把自己的思路清晰的讲出来。不仅是fb ，所有的科技公司都不会浪费时间只招做题机器，让你写代码，只是为了从面试中提取可种信号，看你是否符合要求。我见过不止一个终面一轮代码fail了仍然拿到offer的。

一个general的建议，先跟面试官讨论你的方法，讲清楚并且说出时间、空间复杂度，然后问面试官可以开始coding了吗，得到肯定的答复再写代码。如果写完之后面试官又要求更优的解法，但是又没有时间了，那就是面试官的问题了。

这个东西主要看面试官。他想挂你，有无数个理由…..

如果你能看到面试的反馈，就会发现有些真的很扯，不是说单指脸书。感觉如果能跟面试官单独对线的话，他们的反馈很多站不住脚。

面试说白了对重要的是的词根是inter。双方的互动都可能有问题，可无论面试官本身是什么问题都会造成面试者的失败。这本身就不是一个对等的测试。所以，随它去吧。有人几轮easy，顺利上岸，有人电面就hard，写出来也过不了。

波风水门 发表于 2021-10-16 15:29:49
面试遇到过 deep copy linked list with random pointer 这个问题，说完了基础的 O(n) 空间复杂度的方法之后被面试官要求要 O(1) 的。所以如果面试想不出

给个dp，上周fb的ng vo考到了union find😢

NeedForSpeed 发表于 2021-10-16 23:08
最优当然关键在最字。
不过为了面试时间，很多时候需要取舍。最优不一定好写，写错了反而得不偿失。

比如Morris transverse和quickselect这种感觉一方面写对不容易，另一方面跑testcase时候想讲明白了也很难（尤其面试官不熟悉这俩算法的话），一般的union find写起来不难但是具体到那个比例关系的题就很tricky，这种情况下是不是应该选简单的？并且万一面试官不熟unionfind让证明算法时间复杂度那就。。。至于O(1) copy这种就属于思维上不太好想到并且写起来可能出错的的地方也多了不少。还有一点是比如考了这个算法，讨论的时候需要提到那些更复杂更快的算法吗，尤其当没有信心一定写对复杂算法的时候？

AcForce 发表于 2021-10-17 02:29
一个general的建议，先跟面试官讨论你的方法，讲清楚并且说出时间、空间复杂度，然后问面试官可以开始codin ...

请问讨论的时候需要提到那些复杂算法吗，很多复杂算法确实不容易写对所以倾向于面试中写简单做法

这种问题没什么答案，因为这个场景的变量（面试官）是不定的，有些就喜欢出hard，有些只出medium

其实你就是把最优解都写出来，也一样有可能挂你 XD