n********e
发帖数: 5 | 1 zenefit 电面，
面试官印度哥， 先问背景，
然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
返回值是 boolean value, 详解见以下链接
http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
由于没有给出最优解，挂了。 |
f**********r
发帖数: 2137 | 2 就是2sum变种吧，bst的in-order是sorted array, 搞两个iterator：next, prev就可
以了？
【在 n********e 的大作中提到】
: zenefit 电面，
: 面试官印度哥， 先问背景，
: 然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
: 返回值是 boolean value, 详解见以下链接
: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
: 由于没有给出最优解，挂了。
|
x*****0
发帖数: 452 | |
f********y
发帖数: 156 | 4 谢了，貌似g4g是老印的题库
mark
【在 x*****0 的大作中提到】
: mark
|
j******g
发帖数: 1428 | |
k**l
发帖数: 2966 | 6 这题不能像2sum一样从两头往中间找？
弄两个往前和往后的iterator走到碰头，不过挺麻烦的
【在 n********e 的大作中提到】
: zenefit 电面，
: 面试官印度哥， 先问背景，
: 然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
: 返回值是 boolean value, 详解见以下链接
: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
: 由于没有给出最优解，挂了。
|
k****r
发帖数: 807 | 7 思路就是这样的，但是写起来很麻烦。记得用了两个类似状态基一样的东西。。。。
【在 k**l 的大作中提到】
: 这题不能像2sum一样从两头往中间找？
: 弄两个往前和往后的iterator走到碰头，不过挺麻烦的
|
f******x
发帖数: 201 | 8 我Zenefits一直到final interview都没有遇到这么变态的题目。。。
final interview第一个人可能是三哥也可能是伊朗哥，感觉出的题目也是水水的。
版上有一个大牛说过，如果是三哥，就要reschedule。。。
【在 n********e 的大作中提到】
: zenefit 电面，
: 面试官印度哥， 先问背景，
: 然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
: 返回值是 boolean value, 详解见以下链接
: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
: 由于没有给出最优解，挂了。
|
c*******t
发帖数: 123 | 9 帖个代码，c++,十几行。
bool findPairWithGivenSumInBST(TreeNode* root, int target){
stack inorder,rinorder;
TreeNode *lo=root,*hi=root;
bool move_lo=true,move_hi=true;
while(lo||hi||!inorder.empty()||!rinorder.empty()){
if(move_lo){
while(lo){inorder.push(lo);lo=lo->left;}
lo=inorder.top();inorder.pop();
}
if(move_hi){
while(hi){rinorder.push(hi);hi=hi->right;}
hi=rinorder.top();rinorder.pop();
}
if(lo==hi) return false;
if(lo->val+hi->val==target) return true;
else if(lo->val+hi->valright;move_lo=true;move_hi=
false;}
else{hi=hi->left;move_hi=true;move_lo=false;}
}
return false;
} |
c*******t
发帖数: 123 | 10 祝楼主好运。以后拿大offer，我也是找工作小白一个，
但这里我想说，面试官不满意，不是因为楼主没有给出最优解。
面试时间那么短，什么题都要最优解，不现实。
最主要的是是否抓住了面试官的心理，他想考我什么？他喜欢用什么方法做？
这个题如果读出数据在数组里，是简单，可是题目bst的point在哪呢？那样做是肯定不
行的。
简要的说就是抓住题眼！在30分钟内要说服一个人不太可能。
唯一可能的是顺着他的思路，投其所好。
【在 n********e 的大作中提到】
: zenefit 电面，
: 面试官印度哥， 先问背景，
: 然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
: 返回值是 boolean value, 详解见以下链接
: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
: 由于没有给出最优解，挂了。
|
j**********3
发帖数: 3211 | 11 mark
【在 n********e 的大作中提到】
: zenefit 电面，
: 面试官印度哥， 先问背景，
: 然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
: 返回值是 boolean value, 详解见以下链接
: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
: 由于没有给出最优解，挂了。
|
f*******r
发帖数: 976 | 12 move on
【在 n********e 的大作中提到】
: zenefit 电面，
: 面试官印度哥， 先问背景，
: 然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
: 返回值是 boolean value, 详解见以下链接
: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
: 由于没有给出最优解，挂了。
|
r*******g
发帖数: 1335 | |
s*******h
发帖数: 105 | 14 这个如果可以允许用python写两个generator, 就比较简单了。
【在 n********e 的大作中提到】
: zenefit 电面，
: 面试官印度哥， 先问背景，
: 然后出了一道题， 在bst中找是否有两个nodes 之和 等于k,
: 返回值是 boolean value, 详解见以下链接
: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/
: 由于没有给出最优解，挂了。
|
