y***1
发帖数: 18 | 1 背景： cs Ph.D， 已经毕业工作3年，在学校里做faculty. 本来完全没想过去公司，
前几天不知google recruiter 怎么地就找到我的联系方式问有无兴趣跳槽，那就试试
吧。
昨天面的，背景聊了快20分钟，然后
（1）what is BST?
(2) 可不可以里面有duplicate value.
(3) 如何handle duplicate value, 不同handle 策略有什么优缺点。
（4）然后选了一种我说的，把duplicate全放在left sub tree, 然后写一个function
判断是不是BST, 就是 validateBST
我写了一个最简单的，分析了复杂度， 是O(n^2), 问可不可以optimize,我说可以。
便写了一个O(n)的用low 和high 来bond.
然后程序有个小bug,经提示改了，又问这个方法有什么drawback,我说遇到 root=INT_
MAX, root->right=INT_MAX会overflow, 然后要求处理overflow.
面了50分钟。
今天打电话过来说要onsite.
给大家一个参考。。 | s*w
发帖数: 729 | 2 faculty 多好啊，自由自在当老板
不过你这个面试怎么尽问 coding 了？
function
【在 y***1 的大作中提到】
: 背景： cs Ph.D， 已经毕业工作3年，在学校里做faculty. 本来完全没想过去公司，
: 前几天不知google recruiter 怎么地就找到我的联系方式问有无兴趣跳槽，那就试试
: 吧。
: 昨天面的，背景聊了快20分钟，然后
: （1）what is BST?
: (2) 可不可以里面有duplicate value.
: (3) 如何handle duplicate value, 不同handle 策略有什么优缺点。
: （4）然后选了一种我说的，把duplicate全放在left sub tree, 然后写一个function
: 判断是不是BST, 就是 validateBST
: 我写了一个最简单的，分析了复杂度， 是O(n^2), 问可不可以optimize,我说可以。
| x****g
发帖数: 1512 | | d****n
发帖数: 94 | 4
node >= node所有的左子树节点
node < node所有右子树节点？
【在 x****g 的大作中提到】
: "分析了复杂度， 是O(n^2)" 怎么写的？
| f*********5
发帖数: 576 | 5 BST到底允不允许有重复的？
function
【在 y***1 的大作中提到】
: 背景： cs Ph.D， 已经毕业工作3年，在学校里做faculty. 本来完全没想过去公司，
: 前几天不知google recruiter 怎么地就找到我的联系方式问有无兴趣跳槽，那就试试
: 吧。
: 昨天面的，背景聊了快20分钟，然后
: （1）what is BST?
: (2) 可不可以里面有duplicate value.
: (3) 如何handle duplicate value, 不同handle 策略有什么优缺点。
: （4）然后选了一种我说的，把duplicate全放在left sub tree, 然后写一个function
: 判断是不是BST, 就是 validateBST
: 我写了一个最简单的，分析了复杂度， 是O(n^2), 问可不可以optimize,我说可以。
| s**x
发帖数: 7506 | 6 应该可以吧？ multiset, multimap etc.
【在 f*********5 的大作中提到】
: BST到底允不允许有重复的？
:
: function
| z****s
发帖数: 409 | 7 谁教你的multiset就是BST了？BST的变形 == BST？自己去wiki下BST定义吧。 | z****s
发帖数: 409 | 8 还有这lz是脑残吧？你直接在每个节点上开一个count域不就完了？还放到左子树？你
有病吧。 | e*******s
发帖数: 1979 | 9 发考题显然好
function
【在 y***1 的大作中提到】
: 背景： cs Ph.D， 已经毕业工作3年，在学校里做faculty. 本来完全没想过去公司，
: 前几天不知google recruiter 怎么地就找到我的联系方式问有无兴趣跳槽，那就试试
: 吧。
: 昨天面的，背景聊了快20分钟，然后
: （1）what is BST?
: (2) 可不可以里面有duplicate value.
: (3) 如何handle duplicate value, 不同handle 策略有什么优缺点。
: （4）然后选了一种我说的，把duplicate全放在left sub tree, 然后写一个function
: 判断是不是BST, 就是 validateBST
: 我写了一个最简单的，分析了复杂度， 是O(n^2), 问可不可以optimize,我说可以。
| y***1
发帖数: 18 | 10 这题面试的就是把BST的定义改成了left tree<=root, right tree < root然后让你写
validateBST
★ 发自iPhone App: ChineseWeb 7.8
【在 f*********5 的大作中提到】
: BST到底允不允许有重复的？
:
: function
| | | T*******e
发帖数: 4928 | 11 你好像没看懂题，把简单的BST想成线段树了。
lz答得是对的。
【在 z****s 的大作中提到】
: 还有这lz是脑残吧？你直接在每个节点上开一个count域不就完了？还放到左子树？你
: 有病吧。
| c**y
发帖数: 172 | 12 能解释一下为什么会overflow吗
root->value = MAX_INT and root->right->value = MAX_INT
function
【在 y***1 的大作中提到】
: 背景： cs Ph.D， 已经毕业工作3年，在学校里做faculty. 本来完全没想过去公司，
: 前几天不知google recruiter 怎么地就找到我的联系方式问有无兴趣跳槽，那就试试
: 吧。
: 昨天面的，背景聊了快20分钟，然后
: （1）what is BST?
: (2) 可不可以里面有duplicate value.
: (3) 如何handle duplicate value, 不同handle 策略有什么优缺点。
: （4）然后选了一种我说的，把duplicate全放在left sub tree, 然后写一个function
: 判断是不是BST, 就是 validateBST
: 我写了一个最简单的，分析了复杂度， 是O(n^2), 问可不可以optimize,我说可以。
| y***1
发帖数: 18 | 13 这是我当时写的
bool BST_Helper(TreeNode* root, int low, int high)
{
if(!root) return true;
if(root->val >= low && root->val <= high)
return BST_Helper(root->left, low, root->val)
&& BST_Helper(root->right, root->val+1, high);
else return false;
}
bool isValidBST2(TreeNode* root)
{
if(!root) return true;
return BST_Helper(root, INT_MIN, INT_MAX);
}
你走一下root->val = INT_MAX, root->right 非空就会有overflow
【在 c**y 的大作中提到】
: 能解释一下为什么会overflow吗
: root->value = MAX_INT and root->right->value = MAX_INT
:
: function
| x****g
发帖数: 1512 | 14 内容是整型你比较容易解决，大不了判定一下啊当前值为INT_MAX,右结点必须为空，否
者错。
问题的引起是因为root->val+1划定下界引起的。
如果是浮点，你就不能定值了。
可以这样解决，其实并不需要判断每个结点的上下界。像单边，只要判单界即可。
就像根节点不用判，初始值随意。
bool isValidBST(TreeNode* root)
{
return BST_Helper(root,0,false,0,false);
}
bool BST_Helper(TreeNode* root, int low, bool checkLow, int high, bool
checkHigh)
{
if(root == NULL) return true;
if(checkLow)
{
if(root->val <= low) return false;
}
if(checkHigh)
{
//if(root->val > high) return false; //if BST support same value at
left child.
if(root->val >= high) return false;
}
return
BST_Helper(root->left, low, checkLow, root->val, true) &&
BST_Helper(root->right,root->val,true,high, checkHigh);
}
【在 y***1 的大作中提到】
: 这是我当时写的
: bool BST_Helper(TreeNode* root, int low, int high)
: {
: if(!root) return true;
: if(root->val >= low && root->val <= high)
: return BST_Helper(root->left, low, root->val)
: && BST_Helper(root->right, root->val+1, high);
: else return false;
: }
: bool isValidBST2(TreeNode* root)
| T*******e
发帖数: 4928 | 15 这个方法感觉更robust.
【在 x****g 的大作中提到】
: 内容是整型你比较容易解决，大不了判定一下啊当前值为INT_MAX,右结点必须为空，否
: 者错。
: 问题的引起是因为root->val+1划定下界引起的。
: 如果是浮点，你就不能定值了。
: 可以这样解决，其实并不需要判断每个结点的上下界。像单边，只要判单界即可。
: 就像根节点不用判，初始值随意。
: bool isValidBST(TreeNode* root)
: {
: return BST_Helper(root,0,false,0,false);
: }
|
|
