x****g 发帖数: 109 | 1 Hi everyone,
I just had my first round technical phone interview with Google three days
ago for summer intern.
But I did not get any feedback, nor information about the time of my second
round.
Does this mean I failed the first round?
Here is the question I had and my answer, I think I answered them correctly.
1. Suppose there is a binary search tree, and you are given the in-order
traversal result of this BST, how to re-construct the BST?
My answer: the BST can't be re-constructed, because the |
l*y 发帖数: 21010 | 2 我觉得你答的没错
second
correctly.
【在 x****g 的大作中提到】 : Hi everyone, : I just had my first round technical phone interview with Google three days : ago for summer intern. : But I did not get any feedback, nor information about the time of my second : round. : Does this mean I failed the first round? : Here is the question I had and my answer, I think I answered them correctly. : 1. Suppose there is a binary search tree, and you are given the in-order : traversal result of this BST, how to re-construct the BST? : My answer: the BST can't be re-constructed, because the
|
r**m 发帖数: 163 | 3 没事的,还早,一周以后没反应再发邮件不迟。
bless u!
second
correctly.
【在 x****g 的大作中提到】 : Hi everyone, : I just had my first round technical phone interview with Google three days : ago for summer intern. : But I did not get any feedback, nor information about the time of my second : round. : Does this mean I failed the first round? : Here is the question I had and my answer, I think I answered them correctly. : 1. Suppose there is a binary search tree, and you are given the in-order : traversal result of this BST, how to re-construct the BST? : My answer: the BST can't be re-constructed, because the
|
m*****f 发帖数: 1243 | 4 请问楼主,知道preorder能知道root没错, 然后如何找出左子树和右子树的root, 并且递归? 我似乎有点不明白。
给你interview的那人什么都没说, 也没让你实现, 听完答案就挂了? |
j**0 发帖数: 11 | 5 The nodes following the root in the traversal consist of 2 partitions: those
<= root and those > root. You can use binary search to find the boundary of
these 2 partitions. (linear search also works but it's sub-optimal) Then
the 1st node of these 2 partitions are the roots of the 2 sub trees. Vitit
these 2 partitions recursively. |
d**a 发帖数: 84 | 6 我也觉得没法重建。简单举个例子也可以验证, 两个节点的树,无法知道第二个是在
左边还是右边啊。
并且递归? 我似乎有点不明白。
【在 m*****f 的大作中提到】 : 请问楼主,知道preorder能知道root没错, 然后如何找出左子树和右子树的root, 并且递归? 我似乎有点不明白。 : 给你interview的那人什么都没说, 也没让你实现, 听完答案就挂了?
|
l*****a 发帖数: 14598 | 7 there is another condition named BST
【在 d**a 的大作中提到】 : 我也觉得没法重建。简单举个例子也可以验证, 两个节点的树,无法知道第二个是在 : 左边还是右边啊。 : : 并且递归? 我似乎有点不明白。
|
m*****f 发帖数: 1243 | 8 oh, BST, then it makes sense
【在 l*****a 的大作中提到】 : there is another condition named BST
|
|
d*******n 发帖数: 141 | 9 agree
【在 l*****a 的大作中提到】 : there is another condition named BST
|
g*******y 发帖数: 1930 | 10 才3天,不着急,我觉得一般电面是一周给答复吧,不过不清楚intern的情况
second
correctly.
【在 x****g 的大作中提到】 : Hi everyone, : I just had my first round technical phone interview with Google three days : ago for summer intern. : But I did not get any feedback, nor information about the time of my second : round. : Does this mean I failed the first round? : Here is the question I had and my answer, I think I answered them correctly. : 1. Suppose there is a binary search tree, and you are given the in-order : traversal result of this BST, how to re-construct the BST? : My answer: the BST can't be re-constructed, because the
|
d**a 发帖数: 84 | 11 对啊,忘了这条了
【在 l*****a 的大作中提到】 : there is another condition named BST
|
x******a 发帖数: 39 | 12 我觉得即使知道PREORDER,结果也不唯一啊
比如这个BST
http://upload.wikimedia.org/wikipedia/commons/d/da/Binary_search_tree.svg
如果把节点6及其CHILDREN,移到节点1的rchild,pre-order traversal结果不变啊 |
x******a 发帖数: 39 | |
h****b 发帖数: 157 | 14 I think for BST, in-order can reconstruct since it is the ordered sequence
of the BST |