非死不可 热乎昂赛面经 NEW GRAD

taoli0515 发表于 2018-4-14 04:28
inorder traversal, 要O(1) 就只有threaded morris 和parent pointer吧 还有别的么？

我所知道的就是Morris。 Parent pointer那就得要求input的数据结构就是这样的，不太现实。

lakeshore 发表于 2018-4-14 05:45
真心不易，bar真高，10分钟单单写Morris traversal都够呛。压力之下，楼主已经表现很好了，祝楼主拿offer！

哎，运气不济。不过本来我就是光脚，白赚了面试经验，也不亏了。

楼主写的面筋真的很详细。很优秀的。

ianhezy 发表于 2018-4-14 06:09
楼主写的面筋真的很详细。很优秀的。

也是自我提升的过程

第三题你有没有问三姐如果用递归的话，函数递归调用产生的空间算吗？如果不算的话递归写起来挺容易

LZ我下周onsite，看了你的面经感觉已挂。。请问new grad要准备ood和system design么，祝lz好运offer到手

duduhaha 发表于 2018-4-14 14:59
第三题你有没有问三姐如果用递归的话，函数递归调用产生的空间算吗？如果不算的话递归写起来挺容易

LZ写的iterative，写完后三姐问我有没有考虑过递归。我说递归也算extra space。分析了下递归的空间，balanced LogN, unbalanced N, 和iterative一样。感觉她挺满意。

lbq1993 发表于 2018-4-14 21:08
LZ我下周onsite，看了你的面经感觉已挂。。请问new grad要准备ood和system design么，祝lz好运offer到手

System design肯定不用，OOD我也没看的。考不考我也不知道 感觉是不会的。

lz merge set这题可否说一下具体思路？

idatascience 发表于 2018-4-14 02:53
第一轮就是写depth函数吧，然后diameter就是max(diameter of each children, top two max depth of childre ...

按照层主的思路 似乎不需要union find，凡是element对应两个及以上的set id就union,这里如何输出结果呢?