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 |
