由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - G家电面
相关主题
● 判断是不是binary search tree-leetcode● hasPathSum
● 问一个leetcode上Validate Binary Search Tree的问题● 急！google 一面。请大侠看看
● leetcode valid bst new test cases 过不去了。。。● 大家leetcode的test case都过得去么?我的怎么经常不成?
● 判断BT是否BST?● L家的面试体验让人有些无语
● 请问LC上一道题：Validate BST● 一道面试题
● 问一个题目● 请大神进来看看为什么我的iterative preorder tranverse过不了，多谢
● Time complexity● Interview question::
● 写了个symmetric tree的stack based iterative实现，有个bug● GOOG ONSITE 面试
相关话题的讨论汇总
话题: root话题: isbst话题: return话题: isvalidbst话题: treenode
进入JobHunting版参与讨论
1 (共1页)
w**2
发帖数: 29
1
从版上获益不少，昨天G的店面很不理想，也发下面经吧
阿三面试官到点了 还说要几分钟弄好麦克风。
问了一下bst的性质 就让我写个validate bst的 函数
我想这不是原题吗？就把之前写过的敲了一遍。
public boolean isValidBST(TreeNode root) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(root==null) return true;
int[] last = new int[1];
last[0]=Integer.MIN_VALUE;
return isValidBST(root,last);
}
public boolean isValidBST(TreeNode root, int[] last){
if (root.left!=null){
if(root.val<=root.left.val || !isValidBST(root.left,last))
return false;
}
if (root.val<=last[0]) return false;
last[0]=root.val;
if (root.right!=null){
if(root.val>=root.right.val || !isValidBST(root.right,last))
return false;
}
return true;
}
然后他跟我说 有问题。(root.val<=root.left.val 其实可以不check 但写了也没错阿
)
举了个例子
8
/
4
\
10
说不行,..我说可以阿。
这样折腾了30分钟 之前他浪费了7-8分钟。
最后问我 thread process 的区别。
然后就结束了。
心情很沉重，朋友的推荐给力，但一电面就成这样了。。。
w*****e
发帖数: 931
2
如果只有一个root节点且值为MIN_VALUE岂不是输出false？

reused

【在 w**2 的大作中提到】
: 从版上获益不少，昨天G的店面很不理想，也发下面经吧
: 阿三面试官到点了 还说要几分钟弄好麦克风。
: 问了一下bst的性质 就让我写个validate bst的 函数
: 我想这不是原题吗？就把之前写过的敲了一遍。
: public boolean isValidBST(TreeNode root) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: if(root==null) return true;
: int[] last = new int[1];
: last[0]=Integer.MIN_VALUE;
a***m
发帖数: 5037
3
电面是怎么做代码题的 ？
J****3
发帖数: 427
4
google doc

【在 a***m 的大作中提到】
: 电面是怎么做代码题的 ？
w**2
发帖数: 29
5
你说的是对的。
我在面试中都跟此烙印说了 可以用node数组而不是int 数组，initial的时候放个
null 他说that is fine

【在 w*****e 的大作中提到】
: 如果只有一个root节点且值为MIN_VALUE岂不是输出false？
:
: reused
c***0
发帖数: 449
6
bool isBST(node* cur, int lowBound, int highBound){
if(cur){
if(cur->value > lowBound && cur->value < highBound)
return isBST(cur->left, lowBound, cur->Value) && isBST(cur->
right, cur->value, highBound);
else
return false;
}
return true;
}
请指教。
q******8
发帖数: 848
7
这个写的有点乱。。。
w**2
发帖数: 29
8
回来之后 我朋友也给我写了这个解 用range去限定。
比我的简单 也clean
可能此烙印拿的也是这个解吧。但是说我的不对还是有点过了。
我当时自己练题，也没去找最好的或者最clean的解。

【在 c***0 的大作中提到】
: bool isBST(node* cur, int lowBound, int highBound){
: if(cur){
: if(cur->value > lowBound && cur->value < highBound)
: return isBST(cur->left, lowBound, cur->Value) && isBST(cur->
: right, cur->value, highBound);
: else
: return false;
: }
: return true;
: }
k******4
发帖数: 94
9
这个也是你那本书上推荐的解法之一，但是总有个担心，万一BST中最小的元素等于
lowBound的初始值怎么办？
试着贴个刚在leetcode通过的代码
bool isBST(TreeNode*root, TreeNode*&pre)
{
if(root == NULL)
return true;
if(!isBST(root->left, pre) || (pre != NULL && pre->val >= root->val)
)
return false;
pre = root;
return isBST(root->right, pre);

}
bool isValidBST(TreeNode *root) {
TreeNode *pre = NULL;
return isBST(root,pre);
}

【在 c***0 的大作中提到】
: bool isBST(node* cur, int lowBound, int highBound){
: if(cur){
: if(cur->value > lowBound && cur->value < highBound)
: return isBST(cur->left, lowBound, cur->Value) && isBST(cur->
: right, cur->value, highBound);
: else
: return false;
: }
: return true;
: }
D**********d
发帖数: 849
10
一行代码搞掂
initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
bool IsBST(Tree* root, long long MIN, long long MAX){
return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
left, MIN, root->val) && IsBST(root->right, root->val, MAX);
}
相关主题
● 问一个题目● hasPathSum
● Time complexity● 急！google 一面。请大侠看看
● 写了个symmetric tree的stack based iterative实现，有个bug● 大家leetcode的test case都过得去么?我的怎么经常不成?
进入JobHunting版参与讨论
w**2
发帖数: 29
11
nb 把限定range的逻辑简化成一句
我怕是能写出这个，烙印也可能说是错的。。

【在 D**********d 的大作中提到】
: 一行代码搞掂
: initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
: bool IsBST(Tree* root, long long MIN, long long MAX){
: return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
: left, MIN, root->val) && IsBST(root->right, root->val, MAX);
: }
s*w
发帖数: 729
12
梦鸟你真牛，学习了

【在 D**********d 的大作中提到】
: 一行代码搞掂
: initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
: bool IsBST(Tree* root, long long MIN, long long MAX){
: return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
: left, MIN, root->val) && IsBST(root->right, root->val, MAX);
: }
w**2
发帖数: 29
13
从版上获益不少，昨天G的店面很不理想，也发下面经吧
阿三面试官到点了 还说要几分钟弄好麦克风。
问了一下bst的性质 就让我写个validate bst的 函数
我想这不是原题吗？就把之前写过的敲了一遍。
public boolean isValidBST(TreeNode root) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(root==null) return true;
int[] last = new int[1];
last[0]=Integer.MIN_VALUE;
return isValidBST(root,last);
}
public boolean isValidBST(TreeNode root, int[] last){
if (root.left!=null){
if(root.val<=root.left.val || !isValidBST(root.left,last))
return false;
}
if (root.val<=last[0]) return false;
last[0]=root.val;
if (root.right!=null){
if(root.val>=root.right.val || !isValidBST(root.right,last))
return false;
}
return true;
}
然后他跟我说 有问题。(root.val<=root.left.val 其实可以不check 但写了也没错阿
)
举了个例子
8
/
4
\
10
说不行,..我说可以阿。
这样折腾了30分钟 之前他浪费了7-8分钟。
最后问我 thread process 的区别。
然后就结束了。
心情很沉重，朋友的推荐给力，但一电面就成这样了。。。
w*****e
发帖数: 931
14
如果只有一个root节点且值为MIN_VALUE岂不是输出false？

reused

【在 w**2 的大作中提到】
: 从版上获益不少，昨天G的店面很不理想，也发下面经吧
: 阿三面试官到点了 还说要几分钟弄好麦克风。
: 问了一下bst的性质 就让我写个validate bst的 函数
: 我想这不是原题吗？就把之前写过的敲了一遍。
: public boolean isValidBST(TreeNode root) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: if(root==null) return true;
: int[] last = new int[1];
: last[0]=Integer.MIN_VALUE;
a***m
发帖数: 5037
15
电面是怎么做代码题的 ？
J****3
发帖数: 427
16
google doc

【在 a***m 的大作中提到】
: 电面是怎么做代码题的 ？
w**2
发帖数: 29
17
你说的是对的。
我在面试中都跟此烙印说了 可以用node数组而不是int 数组，initial的时候放个
null 他说that is fine

【在 w*****e 的大作中提到】
: 如果只有一个root节点且值为MIN_VALUE岂不是输出false？
:
: reused
c***0
发帖数: 449
18
bool isBST(node* cur, int lowBound, int highBound){
if(cur){
if(cur->value > lowBound && cur->value < highBound)
return isBST(cur->left, lowBound, cur->Value) && isBST(cur->
right, cur->value, highBound);
else
return false;
}
return true;
}
请指教。
q******8
发帖数: 848
19
这个写的有点乱。。。
w**2
发帖数: 29
20
回来之后 我朋友也给我写了这个解 用range去限定。
比我的简单 也clean
可能此烙印拿的也是这个解吧。但是说我的不对还是有点过了。
我当时自己练题，也没去找最好的或者最clean的解。

【在 c***0 的大作中提到】
: bool isBST(node* cur, int lowBound, int highBound){
: if(cur){
: if(cur->value > lowBound && cur->value < highBound)
: return isBST(cur->left, lowBound, cur->Value) && isBST(cur->
: right, cur->value, highBound);
: else
: return false;
: }
: return true;
: }
相关主题
● L家的面试体验让人有些无语● Interview question::
● 一道面试题● GOOG ONSITE 面试
● 请大神进来看看为什么我的iterative preorder tranverse过不了，多谢● 算法题：如何判断二叉树是AVL？
进入JobHunting版参与讨论
k******4
发帖数: 94
21
这个也是你那本书上推荐的解法之一，但是总有个担心，万一BST中最小的元素等于
lowBound的初始值怎么办？
试着贴个刚在leetcode通过的代码
bool isBST(TreeNode*root, TreeNode*&pre)
{
if(root == NULL)
return true;
if(!isBST(root->left, pre) || (pre != NULL && pre->val >= root->val)
)
return false;
pre = root;
return isBST(root->right, pre);

}
bool isValidBST(TreeNode *root) {
TreeNode *pre = NULL;
return isBST(root,pre);
}

【在 c***0 的大作中提到】
: bool isBST(node* cur, int lowBound, int highBound){
: if(cur){
: if(cur->value > lowBound && cur->value < highBound)
: return isBST(cur->left, lowBound, cur->Value) && isBST(cur->
: right, cur->value, highBound);
: else
: return false;
: }
: return true;
: }
D**********d
发帖数: 849
22
一行代码搞掂
initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
bool IsBST(Tree* root, long long MIN, long long MAX){
return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
left, MIN, root->val) && IsBST(root->right, root->val, MAX);
}
w**2
发帖数: 29
23
nb 把限定range的逻辑简化成一句
我怕是能写出这个，烙印也可能说是错的。。

【在 D**********d 的大作中提到】
: 一行代码搞掂
: initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
: bool IsBST(Tree* root, long long MIN, long long MAX){
: return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
: left, MIN, root->val) && IsBST(root->right, root->val, MAX);
: }
s*w
发帖数: 729
24
梦鸟你真牛，学习了

【在 D**********d 的大作中提到】
: 一行代码搞掂
: initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
: bool IsBST(Tree* root, long long MIN, long long MAX){
: return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
: left, MIN, root->val) && IsBST(root->right, root->val, MAX);
: }
c********p
发帖数: 1969
25
mark
1 (共1页)
进入JobHunting版参与讨论
相关主题
● GOOG ONSITE 面试● 请问LC上一道题：Validate BST
● 算法题：如何判断二叉树是AVL？● 问一个题目
● 请教这么一个题：BST maximum sum path● Time complexity
● 为啥有两个case不对？？Binary Tree Maximum Path Sum● 写了个symmetric tree的stack based iterative实现，有个bug
● 判断是不是binary search tree-leetcode● hasPathSum
● 问一个leetcode上Validate Binary Search Tree的问题● 急！google 一面。请大侠看看
● leetcode valid bst new test cases 过不去了。。。● 大家leetcode的test case都过得去么?我的怎么经常不成?
● 判断BT是否BST?● L家的面试体验让人有些无语
相关话题的讨论汇总
话题: root话题: isbst话题: return话题: isvalidbst话题: treenode

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑