菲斯不可新鲜面经

lzsapril666 发表于 2018-10-16 09:55
请问楼主第一轮是怎么设计那个数据结构的？我的想法是用hashmap记录每个node的parent，相当于构建parent指 ...

O(logN)的LCA是很经典的算法了（虽然在leetcode考纲之外）可以自己google一下
比较容易写的是倍增算法，对每个结点存储和它距离为1、2、4、8……的祖先结点，然后查询的时候用二分法

ML Engineer面试一点ML都不问吗？

lg n的lca可以这样做：
1. 开一个flag数组
2. 让两个node先商议好一个唯一的token，比如当期的timestamp
3. 其中一个node向root回溯，标记所有的ancestor为token
4. 另一个node也向root回溯，遇到标有第一个token的ancestor即为lca

cjlsysu 发表于 2018-10-16 12:50
lg n的lca可以这样做：
1. 开一个flag数组
2. 让两个node先商议好一个唯一的token，比如当期的timestam ...

题目中给出的是Binary Tree，而非Balanced Binary Tree，无法保证树高在logN范围内，所以这种方法复杂度最差也是O(n)
其实这种解法对应的是另外一种follow up，即当每个节点除了指向左右儿子还指向parent，如何优化

Erudite_Li 发表于 2018-10-16 12:18
楼上正解！

big integer 的 case 需要考虑负树的case 吗 要考虑负数的话 感觉不太好coding 啊？

感谢楼主的分享～

Erudite_Li 发表于 2018-10-16 12:27
大家都在问第一题的follow up, 我最后在面试官的提示下想到的解法是用一个int[] 存树中的每一个点（level o ...

这里不是很明白，能举个例子么？

提供一种lgN 查找时间的方法 https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-3-using-rmq/

Erudite_Li 发表于 2018/10/16 12:22:47


啊？我也不知道啊，HR说现在要开始team match了。我确实也有同学没有team match。

博士要match 本科直接给offer了

来自一亩三分地官方APP

edyyy 发表于 2018-10-17 10:08
博士要match 本科直接给offer了

来自一亩三分地官方APP

原来如此