r*****e
发帖数: 30 | 1 国内小伙伴，刚面fb，分享一下题目和答案
给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个node
，O(1) space和 O(log N) time的解法，有Parent指针
struct node{
int val;
node* left;
node* right;
node* parent;
node(int v){
val = v;
parent = left = right = NULL;
}
};
node* find(node* root, int val){
if(!root) return NULL;
if(root->val == val) return root;
if(root->val < val) return find(root->right, val);
return find(root->left, val);
}
node* next(node* n){
if(!n) return NULL;
if(n->right){
node* p = n->right;
while(p->left) p = p->left;
return p;
}
p = n->parent;
while(p){
if(p->left == n) break;
n = p;
p = p->parent;
}
return p;
} |
r*****e
发帖数: 30 | 2 给定一个vector> v
其中string表示user id， int表示该user发帖数，找出发帖最多的k个用户
void kth(vector>& v, int begin, int end, int k){
if(end-begin+1
int i = begin, j = end;
pair pivot = v[end];
while(i < j){
while(i < j && v[i].second >= pivot.second) i++;
if(i < j) v[j--] = v[i];
while(i < j && v[j].second <= pivot.second) j--;
if(i < j) v[i++] = v[j];
}
v[i] = pivot;
if(i-begin+1 == k) return ;
if(i-begin+1 < k) return kth(v, i+1, end, k-(i-begin+1));
return kth(v, begin, i-1, k);
} |
l*******0
发帖数: 95 | 3 就是找后继节点呀
if node.right ! = null
return maxNode(node.right);
else
Node parent = node.parent;
while(parent.right == node) {
node = parent;
parent = node.parent;
}
return parent; |
w*****t
发帖数: 485 | 4 赞楼主分享！
是在国内面的吗？
【在 r*****e 的大作中提到】
: 国内小伙伴，刚面fb，分享一下题目和答案
: 给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个node
: ，O(1) space和 O(log N) time的解法，有Parent指针
: struct node{
: int val;
: node* left;
: node* right;
: node* parent;
: node(int v){
: val = v;
|
f********a
发帖数: 367 | 5 forgot to check for null after Node parent = node.parent;
【在 l*******0 的大作中提到】
: 就是找后继节点呀
: if node.right ! = null
: return maxNode(node.right);
: else
: Node parent = node.parent;
: while(parent.right == node) {
: node = parent;
: parent = node.parent;
: }
: return parent;
|
w*****t
发帖数: 485 | 6 恩，总体难度如何？ 设计题呢？
【在 r*****e 的大作中提到】
: 给定一个vector> v
: 其中string表示user id， int表示该user发帖数，找出发帖最多的k个用户
: void kth(vector>& v, int begin, int end, int k){
: if(end-begin+1 : int i = begin, j = end;
: pair pivot = v[end];
: while(i < j){
: while(i < j && v[i].second >= pivot.second) i++;
: if(i < j) v[j--] = v[i];
: while(i < j && v[j].second <= pivot.second) j--;
|
w*****t
发帖数: 485 | 7 pivot的选取有要求吗？
【在 r*****e 的大作中提到】
: 给定一个vector> v
: 其中string表示user id， int表示该user发帖数，找出发帖最多的k个用户
: void kth(vector>& v, int begin, int end, int k){
: if(end-begin+1 : int i = begin, j = end;
: pair pivot = v[end];
: while(i < j){
: while(i < j && v[i].second >= pivot.second) i++;
: if(i < j) v[j--] = v[i];
: while(i < j && v[j].second <= pivot.second) j--;
|
r*****e
发帖数: 30 | |
r*****e
发帖数: 30 | |
f********a
发帖数: 367 | 10 this looks like a phone interview .... |
|
|
m******a
发帖数: 84 | |
r*****e
发帖数: 30 | |
l**o
发帖数: 25 | 13 哪两道? 透露一下呗
【在 r*****e 的大作中提到】
: 还有两道lc的题，fb一定有设计题？
|
j*****g
发帖数: 47 | 14 bst题的那一轮中，还有一题是什么？还是这轮中只有bst一题？ |
h***k
发帖数: 161 | 15 第二题是找第k个还是前k个？不熟悉c++，能细讲下思路吗 |
r*****e
发帖数: 30 | 16 reverse string
jump game
没有设计题 |
