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

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

顶这个回复
面google被考过Morris，向recruiter反应了说并没有问题，无话可说😶
至今想起来心里还是要骂一声
非常败我曾经那么一点对狗家的好感

个人感觉，union find这种已经很简单了。而且不容易写错。
反而是morris这种道理容易理解，但是写起来比较tricky。
quick select介于二者之间。
至于kmp这种才是又难记又难写。

pandami 发表于 2021-10-17 11:48
个人感觉，union find这种已经很简单了。而且不容易写错。
反而是morris这种道理容易理解，但是写起来比较t ...

同感，一般的unionfind还算好写，但也有散酒酒这种魔改unionfind难度明显加大

zfaker 发表于 2021-10-17 09:02:26
比如Morris transverse和quickselect这种感觉一方面写对不容易，另一方面跑testcase时候想讲明白了也很难（尤其面试官不熟悉这俩算法的话），一般的union find写起来

我觉得写简单的比较靠谱，后面说一下优化

地里新人，请问电面阶段过不过是面试官一人说了算吗？
记得面试官面试时候在做笔记，还以为是把笔记在committee里大家一起讨论呢。

zfaker 发表于 2021-10-17 09:04
请问讨论的时候需要提到那些复杂算法吗，很多复杂算法确实不容易写对所以倾向于面试中写简单做法

可以在follow up的时候提

必须要bug free啊

有人面试被要求kmp吗？？

如果最优解和次优解难度相差巨大， 比如LC 287这种， SC O(n) vs O(1), 如果你给个SC  O(n)的解，肯定会让你挂
如果最优解和次优解难度相差不大的情况下， 就看你的运气了， 当然 如果你communication到位， edge case找得好， 还是很有机会过的

波风水门 发表于 2021-10-16 18:29
面试遇到过 deep copy linked list with random pointer 这个问题，说完了基础的 O(n) ...

有理有据又严谨，感谢层主