i*******g
发帖数: 100 | 1 Amazon的面试，递进式的
1） 如何在binary tree找一个path 从root 到leaf, 和是sum?
2) 如何序列化一个binary tree到一个文件
3) 如果有一个已经序列化的tree, 很大，要做1)的算法，怎么做，2）中如果有多个
方法选择哪中序列化的方法比较好？
4） 如果有1000w个已经序列化的小文件，对他们都要做3），如何提高性能，系统是5
台机器 | i****c
发帖数: 102 | 2 这题有意思！
1）easy, recursive or iterative algorithm
2) preorder+inorder, preorder+marker, level-by-level, etc.
3) I will prefer to use preorder+marker so that we can find the path to
leaves
without constructing trees in memory
A quick thought, we can do serilization by repeating parent nodes (correct
me if you find errors)
e.g., a tree, root is A, A's left is B, right is C, B's right is D, and C's
left and right are E and F respectively.
then we have AB?DACECF, ? indicates a null
4) distribute small files to different machines and solve them in each
machine.
for huge trees, we can distributed subtrees recursively to different
machines.
e.g. AB?DACECF can be divided into two parts: AB?D, and ACECF
5
【在 i*******g 的大作中提到】
: Amazon的面试，递进式的
: 1） 如何在binary tree找一个path 从root 到leaf, 和是sum?
: 2) 如何序列化一个binary tree到一个文件
: 3) 如果有一个已经序列化的tree, 很大，要做1)的算法，怎么做，2）中如果有多个
: 方法选择哪中序列化的方法比较好？
: 4） 如果有1000w个已经序列化的小文件，对他们都要做3），如何提高性能，系统是5
: 台机器
| b*******8
发帖数: 37364 | 3 问一下，这种阶梯式题目，难度递进的，是不是就是要看你能走多远？全走完等于打败
老怪了吧？ | i*******g
发帖数: 100 | 4 我到最后了，跟imusic的答案类似
1） recursive, 判定leaf的exit point，我们讨论了一下
2） 比较多方法，随后发信给interviewer了
3） 我当时解释了，由于1）的算法选择，因此序列化的时候如果能够按tree的level存
储会达到比较好的save space的效果，但没有详述
4） zip后distribute, 另外可以map reduce, 不过他让提自己的方案，也是简述，主
要是考虑要用尽运算时的I/O
不过人还是没让进下一轮,但是并没有放到block list只是说找了别人，另外是要找js的
人，吐了一升血，做js，却问我这么多其他~~~ | p*****a
发帖数: 147 | 5
s
then we have AB?DACECF, ? indicates a null
~~~~~~~~~~marker是？?,这里怎么两个C?
【在 i****c 的大作中提到】
: 这题有意思！
: 1）easy, recursive or iterative algorithm
: 2) preorder+inorder, preorder+marker, level-by-level, etc.
: 3) I will prefer to use preorder+marker so that we can find the path to
: leaves
: without constructing trees in memory
: A quick thought, we can do serilization by repeating parent nodes (correct
: me if you find errors)
: e.g., a tree, root is A, A's left is B, right is C, B's right is D, and C's
: left and right are E and F respectively.
| i****c
发帖数: 102 | 6 marker可以有很多种
严格说，我这里用得不是marker，是repeat parent node。我也还没深想是否总能保证
一一对应
C和A出现两次，因为它们有两个子节点 | i****c
发帖数: 102 | 7 for 3) I guess the major purpose is not to save space. Instead, is to get th
e path when parsing (and without constructing a tree in memory)
Also, level-based serialization is not necessary to save much space comparin
g with pre-order+in order or other methods.
js的
【在 i*******g 的大作中提到】
: 我到最后了，跟imusic的答案类似
: 1） recursive, 判定leaf的exit point，我们讨论了一下
: 2） 比较多方法，随后发信给interviewer了
: 3） 我当时解释了，由于1）的算法选择，因此序列化的时候如果能够按tree的level存
: 储会达到比较好的save space的效果，但没有详述
: 4） zip后distribute, 另外可以map reduce, 不过他让提自己的方案，也是简述，主
: 要是考虑要用尽运算时的I/O
: 不过人还是没让进下一轮,但是并没有放到block list只是说找了别人，另外是要找js的
: 人，吐了一升血，做js，却问我这么多其他~~~
| i**9
发帖数: 351 | 8
第一个是要判断存在一个path还是要打印出这么个path?如果要打印的话，有什么更有
效地算法（除了
保存所有可能的path）
5
【在 i*******g 的大作中提到】
: Amazon的面试，递进式的
: 1） 如何在binary tree找一个path 从root 到leaf, 和是sum?
: 2) 如何序列化一个binary tree到一个文件
: 3) 如果有一个已经序列化的tree, 很大，要做1)的算法，怎么做，2）中如果有多个
: 方法选择哪中序列化的方法比较好？
: 4） 如果有1000w个已经序列化的小文件，对他们都要做3），如何提高性能，系统是5
: 台机器
|
|
