淘宝2012校招题目，高手们请进

fanronghua

用你的步骤简化的说， 就是：


所以， 即便不和算深度比， 和小狗撒尿来比， 只有一个优点， 就是不用第 ...
zylthinking 发表于 2011-09-22 16:07

    你说的没有错，在最差的情况下，空间确实存在问题。

    但是按照你的那个办法，即使在最优的情况下，（我说的第一种情况下），你的程序已经死掉了。

mirnshi

这个应该比小狗撒尿的算法要好； 但还可以改进

3，比较节点的深度，移动较深得那个节点得游标指向其 ...
zylthinking 发表于 2011-09-22 12:13

   这个算法很好

mpstat

你们难道就没考虑过这颗树的节点没有存父结点信息的情况？

zylthinking

你说的没有错，在最差的情况下，空间确实存在问题。

    但是按照你的那个办法，即使在最优的 ...
fanronghua 发表于 2011-09-22 16:13

我为什么死掉呢， 你能走2亿步， 我就不能了吗？

fanronghua

如果深度2亿， 其他方法至少可以活着计算， 就算花了几百年， 也不会死掉； 而你的照样是2亿， 还背着一 ...
zylthinking 发表于 2011-09-22 16:10

    你这个想法有问题，关于快速存储，和快速查找的 算法多的是，
   关于存储 2亿个节点 ，我们算一个节点100个自己， 2 0000 0000 × 100 = 20M 的数据.
   可以分块，什么哈希表 。。。。。。 N种办法搞定。

zylthinking

你们难道就没考虑过这颗树的节点没有存父结点信息的情况？
mpstat 发表于 2011-09-22 16:16

无父节点的树存在2亿个叶节点， 是什么树？

manULinux

嗯以上同学们说的都不错哦。在看看 题目
“一颗树上有海量结点，假设在亿这个级别，现在给定任意2个结点（非根结点），请找出他们共同的祖先结点，请在节省空间的前提下，高效查找。
注意：请勿对该树对做任何假设，它不一定是平衡树，也不一定有序。请高手们指教。”

”假设在亿这个级别 “ 这个我理解是不管树是不是 “平衡树，也不一定有序”  如果把树2个节点同时向上找服节点递推没找一次比较一次是不是相同父节点，相同就是了不同继续要。  最差就根就是他们共同的父节点。不用计算深度，和递归路径呀。 总会在亿-N级中找到相同的。 空间就是2个临时节点的父节点信息。

fanronghua

我为什么死掉呢， 你能走2亿步， 我就不能了吗？
zylthinking 发表于 2011-09-22 16:17

    我说你这个办法不是最优的方案。在我 （1）的例子里，我只要走一步就可以得到结果，
你要走两亿步，才得到结果。

fanronghua

嗯以上同学们说的都不错哦。在看看 题目
“一颗树上有海量结点，假设在亿这个级别，现在给定任意2个结点（ ...
manULinux 发表于 2011-09-22 16:19

    你的观点，和我的一样，我觉得这个是最优的方案。

zylthinking

不知你说的是啥意思， 但

2 0000 0000 × 100 = 20M

fanronghua 发表于 2011-09-22 16:18

为简单， 按 1024 = 1000 算
不知你怎么算出来的， M ＝ 1000 K   = 1000 * 1000  = 10000 * 100 = 100万
20 M = 20 * 100万 = 2000万，

2亿 ＝ 20 * 1000万 ＝ 10 ＊ 2000万 = 10 * 20M = 200M
8字节 * 200 M = 1600M

而且， 所谓快速查找算法， 比较排序最快也就是  N * ln(N),   这还是理论上的， 而你所做的查找次数最坏情况还是 2亿 级别的。