处女面－Zillow电面

是的 。可以优化到O(1) space.  但是不容易想

shinichish 发表于 2014-11-22 10:59
这样复杂度太高了。。我觉得先用parent指针找root，然后分治找LCA。BTW，楼主你的算法不是O(logn)的，考 ...

多谢补充！没错！他出题时候提到了，就考虑平衡树，所以我也没多想，就给了他O(logn)

感谢分享！
上的Web课在用Zillow的API
楼主加油！

lz你这个做法不算time: O(logN)吧， 保存了hashset之后遍历另一个node的时候每遇到一个parent 都要在hashset里面找存不存在这个node  这个查找本身就是logN了
所以logN = H, 应该是O(H^2) ?

如果不用额外空间的话 就BFS找出层数 然后一起往上

或者两个NODE走到根 然后反过来找第一个不同的点。。 毕竟HASH不是严格的O(1) 当然hash也可以

guii 发表于 2014-11-22 11:08
多谢补充！没错！他出题时候提到了，就考虑平衡树，所以我也没多想，就给了他O(logn)

加油楼主！我提交了zillow的assignment，2周过去了，为啥还是没有任何消息。。。

shinichish 发表于 2014-11-22 13:18
加油楼主！我提交了zillow的assignment，2周过去了，为啥还是没有任何消息。。。

貌似他们有点儿忙，本来这周给我二面，结果HR说他们太忙改到下周了。加油啦

guii 发表于 2014-11-22 13:26
貌似他们有点儿忙，本来这周给我二面，结果HR说他们太忙改到下周了。加油啦

嗯，加油

时间的确很难再优化了，空间优化的话就是让两个节点到达同样的深度（通过parent可以方便的计算出深度信息）然后再同时网上寻找第一个共同的节点

pyemma 发表于 2014-11-23 09:49
时间的确很难再优化了，空间优化的话就是让两个节点到达同样的深度（通过parent可以方便的计算出深度信息） ...

有道理，我去实现一下