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); : }
|
|