p*****u
发帖数: 310 | 1 今天一面，别的都还好。最后一个检查BST是否valid的题。我非常sure我的code是对的
，但对方却不理解，说没check root大于 left的right。我试着run个例子给她，却又没有足够的时间。大家说这种情况怎
么办？要是就这样fail的话，我真的觉得太不公平了。
这是面试时google docs里的code
bool isValidBST(node * r, int upp, int lower)// input
{
if ( !r ) return true;
if ((r->data< lower) || (r->data > upper)) return false;
if ( ! isValidBST( r->left, r->data, lower))//3 as upper when call l1,
(l1 3, lower) (R2, 3. L2)
return false;
if (! isValidBST(r->right, upp, r->data))
return false;
return true;
}
| w*******e
发帖数: 1588 | 2 The code would return true for the following tree, which is actually invalid.
5
/\
3 8
/\
1 6
The key is every BST node's data must be greater or equals to those of ALL
the nodes of its left sub-tree. | g*****k
发帖数: 623 | 3 your code seems right to me, just could not understand your comment line,
which is very confusing.
又没有足够的时间。大家说这种情况怎
,
【在 p*****u 的大作中提到】
: 今天一面，别的都还好。最后一个检查BST是否valid的题。我非常sure我的code是对的
: ，但对方却不理解，说没check root大于 left的right。我试着run个例子给她，却又没有足够的时间。大家说这种情况怎
: 么办？要是就这样fail的话，我真的觉得太不公平了。
: 这是面试时google docs里的code
: bool isValidBST(node * r, int upp, int lower)// input
: {
: if ( !r ) return true;
: if ((r->data< lower) || (r->data > upper)) return false;
: if ( ! isValidBST( r->left, r->data, lower))//3 as upper when call l1,
: (l1 3, lower) (R2, 3. L2)
| p*****u
发帖数: 310 | 4 请 ignore comment line。 那是我试着run一个例子时写的。可时间太紧，她没听明白。 | g*****k
发帖数: 623 | 5 code是对的，但是没有解释明白，
对方可能要你简洁地讲述算法和你的思路。
你只需要说这是一个递归算法，对于以r为root的子树进行判断是否所有的子节点都在
（low, high)区间。
递归过程就是首先判断当前根节点是否在此区间。
然后再递归判断左子树和右子树在相应改写过的区间。
新的区间将是(low, r.data) 和 (r.data, high)。以为左子树所有节点要小于当前节
点，
右子树要大于当前节点。
白。
【在 p*****u 的大作中提到】
: 请 ignore comment line。 那是我试着run一个例子时写的。可时间太紧，她没听明白。
| p*****u
发帖数: 310 | 6 不会的， 她也是这样说的。 其实call 5的 左子树3的时候， 5就作为upper bound传
下去了，在call 3的右子树6的时候， 6得到3的 upperbound，就是5，所以这是检查了
的。
IsvaidBST（5－>left, 5, INT_MIN) then
IsvaidBST（3－>right, 5, 3)
invalid.
【在 w*******e 的大作中提到】
: The code would return true for the following tree, which is actually invalid.
: 5
: /\
: 3 8
: /\
: 1 6
: The key is every BST node's data must be greater or equals to those of ALL
: the nodes of its left sub-tree.
| p*****u
发帖数: 310 | 7 我说了，可是被打断了，然后就说我没检查root和左子树的右孩子的大小，再想解释，
就没时间了。其实我很诧异，这本是标准解法，我都不知到interviewer心中的解法是
怎样的。
对方是个老中女的，肯定不是cs出身的。大家说我还能怎么argue吗？就此阵亡，实在
不甘心呀。多谢多谢。
【在 g*****k 的大作中提到】
: code是对的，但是没有解释明白，
: 对方可能要你简洁地讲述算法和你的思路。
: 你只需要说这是一个递归算法，对于以r为root的子树进行判断是否所有的子节点都在
: （low, high)区间。
: 递归过程就是首先判断当前根节点是否在此区间。
: 然后再递归判断左子树和右子树在相应改写过的区间。
: 新的区间将是(low, r.data) 和 (r.data, high)。以为左子树所有节点要小于当前节
: 点，
: 右子树要大于当前节点。
:
| g*****k
发帖数: 623 | 8 comfort, you'll get used to it. Shit happens.
Move on.
【在 p*****u 的大作中提到】
: 我说了，可是被打断了，然后就说我没检查root和左子树的右孩子的大小，再想解释，
: 就没时间了。其实我很诧异，这本是标准解法，我都不知到interviewer心中的解法是
: 怎样的。
: 对方是个老中女的，肯定不是cs出身的。大家说我还能怎么argue吗？就此阵亡，实在
: 不甘心呀。多谢多谢。
| g**********y
发帖数: 14569 | 9 code写在那里，哪怕她当时有误会，拿回去也应该可以看明白。最后拿不拿到onsite,
应该跟这个题无关。
安心等一下吧。Bless。
【在 p*****u 的大作中提到】
: 我说了，可是被打断了，然后就说我没检查root和左子树的右孩子的大小，再想解释，
: 就没时间了。其实我很诧异，这本是标准解法，我都不知到interviewer心中的解法是
: 怎样的。
: 对方是个老中女的，肯定不是cs出身的。大家说我还能怎么argue吗？就此阵亡，实在
: 不甘心呀。多谢多谢。
| p*****u
发帖数: 310 | 10 就怕她不看呀。而且既然面试别人这道题，面试官难道不应该知道解法吗？这是最常见
的解法了。我其实认识google挺多人的，也知道面试官的邮箱，想让他们内部的人去说
说，又怕这样更惹人反感。其实我都忍不住说让她get second opinion了。
这道题已经是这次面试最难的题了， 别的更简单。如果拿不到onsite肯定是因为这个
啦。
明天二面 facebook。 唉，毫无心情呀。
,
【在 g**********y 的大作中提到】
: code写在那里，哪怕她当时有误会，拿回去也应该可以看明白。最后拿不拿到onsite,
: 应该跟这个题无关。
: 安心等一下吧。Bless。
| | | w*******e
发帖数: 1588 | 11 Sorry, my bad. Your code was right. I somehow misunderstood the code just
like the interviewer did, as it's sort of easy to get confused. It would
help to make thing more readable, if you added a comment on top like this:
// For caller: IsValidBST（root, INT_MAX, INT_MIN)
It also helps to walk the interviewer through the code, as you just
explained to me :) Good luck!
【在 p*****u 的大作中提到】
: 不会的， 她也是这样说的。 其实call 5的 左子树3的时候， 5就作为upper bound传
: 下去了，在call 3的右子树6的时候， 6得到3的 upperbound，就是5，所以这是检查了
: 的。
: IsvaidBST（5－>left, 5, INT_MIN) then
: IsvaidBST（3－>right, 5, 3)
:
: invalid.
| b*******8
发帖数: 37364 | 12 最后的
if (! isValidBST(r->right, upp, r->data))
return false;
return true;
可以直接简化成 return isValidBST(r->right, upp, r->data);
又没有足够的时间。大家说这种情况怎
,
【在 p*****u 的大作中提到】
: 今天一面，别的都还好。最后一个检查BST是否valid的题。我非常sure我的code是对的
: ，但对方却不理解，说没check root大于 left的right。我试着run个例子给她，却又没有足够的时间。大家说这种情况怎
: 么办？要是就这样fail的话，我真的觉得太不公平了。
: 这是面试时google docs里的code
: bool isValidBST(node * r, int upp, int lower)// input
: {
: if ( !r ) return true;
: if ((r->data< lower) || (r->data > upper)) return false;
: if ( ! isValidBST( r->left, r->data, lower))//3 as upper when call l1,
: (l1 3, lower) (R2, 3. L2)
| b*******8
发帖数: 37364 | 13 还应该提一下调用的时候用
isValidBST(root, INT_MAX, INT_MIN) | a**********2
发帖数: 340 | 14 我觉得应该不会有问题的，可能他自己没看仔细，回去研究一下就反应过来了，我觉得
google docs和collabedit应该增加一个画图功能，一边画一边说更容易沟通，anyway
， bless！ | a********m
发帖数: 15480 | 15 这个就是最难的题了？有点太简单了。没有难题不是好兆头。
不管怎么说，bless.
【在 p*****u 的大作中提到】
: 就怕她不看呀。而且既然面试别人这道题，面试官难道不应该知道解法吗？这是最常见
: 的解法了。我其实认识google挺多人的，也知道面试官的邮箱，想让他们内部的人去说
: 说，又怕这样更惹人反感。其实我都忍不住说让她get second opinion了。
: 这道题已经是这次面试最难的题了， 别的更简单。如果拿不到onsite肯定是因为这个
: 啦。
: 明天二面 facebook。 唉，毫无心情呀。
:
: ,
| P**********c
发帖数: 3417 | 16 我觉得这个没太大问题。google的电面其实bar不高，应该能过。
又没有足够的时间。大家说这种情况怎
,
【在 p*****u 的大作中提到】
: 今天一面，别的都还好。最后一个检查BST是否valid的题。我非常sure我的code是对的
: ，但对方却不理解，说没check root大于 left的right。我试着run个例子给她，却又没有足够的时间。大家说这种情况怎
: 么办？要是就这样fail的话，我真的觉得太不公平了。
: 这是面试时google docs里的code
: bool isValidBST(node * r, int upp, int lower)// input
: {
: if ( !r ) return true;
: if ((r->data< lower) || (r->data > upper)) return false;
: if ( ! isValidBST( r->left, r->data, lower))//3 as upper when call l1,
: (l1 3, lower) (R2, 3. L2)
| v**m
发帖数: 706 | | n**e
发帖数: 116 | 18 Your code looks works to me, but not elegant.
See the following for your reference:
template
bool isBst(Node* node, T low, T high) {
if (node == NULL) return true;
if (node->data < low && node->data > high) return false;
return isBst(node->left, low, node->data
&& isBst(node->right, node->data, high);
}
template
bool isBst(Node* root) {
return isBst(root, limits::min(), limits::max());
} | P**********c
发帖数: 3417 | 19 我onsite也遇到过类似情况，也是recursive程序。怎么解释对方也不信，我又不能说我准备过。我是觉得interviewer要是觉得自己recursive没有那么好，还是不要问
recursive的问题比较好。这种程序很tricky, 如果理解不是那么深入，用来判断别人
风险还是挺大的。
当然我还是觉得你这个问题不大，个人觉得G的onsite不难拿，不需要让面试官觉得一点错误没有。但是onsite真的很难，不知不觉就被据了。
又没有足够的时间。大家说这种情况怎
,
【在 p*****u 的大作中提到】
: 今天一面，别的都还好。最后一个检查BST是否valid的题。我非常sure我的code是对的
: ，但对方却不理解，说没check root大于 left的right。我试着run个例子给她，却又没有足够的时间。大家说这种情况怎
: 么办？要是就这样fail的话，我真的觉得太不公平了。
: 这是面试时google docs里的code
: bool isValidBST(node * r, int upp, int lower)// input
: {
: if ( !r ) return true;
: if ((r->data< lower) || (r->data > upper)) return false;
: if ( ! isValidBST( r->left, r->data, lower))//3 as upper when call l1,
: (l1 3, lower) (R2, 3. L2)
| a********m
发帖数: 15480 | 20 对了。是店面。那如果面试官回头看看的话还是有机会的。
【在 P**********c 的大作中提到】
: 我觉得这个没太大问题。google的电面其实bar不高，应该能过。
:
: 又没有足够的时间。大家说这种情况怎
: ,
| a*o
发帖数: 54 | 21 写封信解释一下？如果不知道对方信箱就请recruiter转一下。我电面时更差，开始没
想出最优解法，刚放下电话就明白过来了，然后立刻写了个程序发给recruiter转过去
，后来也就拿到onsite了
又没有足够的时间。大家说这种情况怎
,
【在 p*****u 的大作中提到】
: 今天一面，别的都还好。最后一个检查BST是否valid的题。我非常sure我的code是对的
: ，但对方却不理解，说没check root大于 left的right。我试着run个例子给她，却又没有足够的时间。大家说这种情况怎
: 么办？要是就这样fail的话，我真的觉得太不公平了。
: 这是面试时google docs里的code
: bool isValidBST(node * r, int upp, int lower)// input
: {
: if ( !r ) return true;
: if ((r->data< lower) || (r->data > upper)) return false;
: if ( ! isValidBST( r->left, r->data, lower))//3 as upper when call l1,
: (l1 3, lower) (R2, 3. L2)
|
|
