m*****k
发帖数: 64 | 1 问了我之前一个用了Google Map API的实习。 问了在一个web implementation里面需
要注意的
事宜。我们讨论了，front end performance optimization和security holes. 问了怎
么样
实现Object-oriented concept in JavaScript, 怎样实现scope,private,closure
inheritance in JavaScript. 最有让我写程序，how to find N-th largest element
in a BST. 写完后他也同意我的程序基本正确，但不是最好的。不过面试完，我才发现
，我的方法忘
了考虑重复的值，比如说1,2,2,2,3 。。。。。。也不知道严重不。。。。。。。
求大家的bless 谢谢！ |
H*M
发帖数: 1268 | 2 bless louzhu!
element
【在 m*****k 的大作中提到】
: 问了我之前一个用了Google Map API的实习。 问了在一个web implementation里面需
: 要注意的
: 事宜。我们讨论了，front end performance optimization和security holes. 问了怎
: 么样
: 实现Object-oriented concept in JavaScript, 怎样实现scope,private,closure
: inheritance in JavaScript. 最有让我写程序，how to find N-th largest element
: in a BST. 写完后他也同意我的程序基本正确，但不是最好的。不过面试完，我才发现
: ，我的方法忘
: 了考虑重复的值，比如说1,2,2,2,3 。。。。。。也不知道严重不。。。。。。。
: 求大家的bless 谢谢！
|
r****o
发帖数: 1950 | 3 怎么找N-th largest elelment in BST?
我想的是用in-order travel，然后找第N个Visit的元素。这种方法可以吗？
还有更好的方法吗？
element
【在 m*****k 的大作中提到】
: 问了我之前一个用了Google Map API的实习。 问了在一个web implementation里面需
: 要注意的
: 事宜。我们讨论了，front end performance optimization和security holes. 问了怎
: 么样
: 实现Object-oriented concept in JavaScript, 怎样实现scope,private,closure
: inheritance in JavaScript. 最有让我写程序，how to find N-th largest element
: in a BST. 写完后他也同意我的程序基本正确，但不是最好的。不过面试完，我才发现
: ，我的方法忘
: 了考虑重复的值，比如说1,2,2,2,3 。。。。。。也不知道严重不。。。。。。。
: 求大家的bless 谢谢！
|
r****o
发帖数: 1950 | 4 弱问，front-end到底是干嘛的啊?
【在 H*M 的大作中提到】
: bless louzhu!
:
: element
|
m*****k
发帖数: 64 | 5 其实我就是用这个方法的，但是如果有重复的值就不灵了吧，比如1,2,2,2,3 3rd
largest 是 1
【在 r****o 的大作中提到】
: 怎么找N-th largest elelment in BST?
: 我想的是用in-order travel，然后找第N个Visit的元素。这种方法可以吗？
: 还有更好的方法吗？
:
: element
|
m*****k
发帖数: 64 | 6 比如说 Google Map, Gmail 的前台Ajax。
【在 r****o 的大作中提到】
: 弱问，front-end到底是干嘛的啊?
|
r****o
发帖数: 1950 | 7 那就再存一个数组，把前几个元素保存下来，就可以知道非重复的第N大元素了把
BTW，3rd larget 应该是3把?
【在 m*****k 的大作中提到】
: 其实我就是用这个方法的，但是如果有重复的值就不灵了吧，比如1,2,2,2,3 3rd
: largest 是 1
|
m*****k
发帖数: 64 | 8 我的理解是 1st largest is 3, 2nd largest is 2, 3rd largest is 1。
【在 r****o 的大作中提到】
: 那就再存一个数组，把前几个元素保存下来，就可以知道非重复的第N大元素了把
: BTW，3rd larget 应该是3把?
|
r****o
发帖数: 1950 | 9 呵呵，不好意思我看错了。
【在 m*****k 的大作中提到】
: 我的理解是 1st largest is 3, 2nd largest is 2, 3rd largest is 1。
|
g*******y
发帖数: 1930 | 10 顺序统计量并没要求要严格的greater than吧？只要是排序后的第N个就行了吧
我觉得lz不用担心这个啦~
【在 m*****k 的大作中提到】
: 我的理解是 1st largest is 3, 2nd largest is 2, 3rd largest is 1。
|
|
|
m*****k
发帖数: 64 | 11 不知道啊，觉得好心虚啊！
【在 g*******y 的大作中提到】
: 顺序统计量并没要求要严格的greater than吧？只要是排序后的第N个就行了吧
: 我觉得lz不用担心这个啦~
|
z*********3
发帖数: 37 | 12 我也觉得不用担心有重复的问题
bless
【在 m*****k 的大作中提到】
: 不知道啊，觉得好心虚啊！
|
m*****k
发帖数: 64 | 13 谢谢你们！
【在 z*********3 的大作中提到】
: 我也觉得不用担心有重复的问题
: bless
|
c*****o
发帖数: 178 | 14 弱问一下，第N大元素不应该是从后数第N个吗？inorder访问的第N个是从头数N个阿。 |
r****o
发帖数: 1950 | 15 You are right
【在 c*****o 的大作中提到】
: 弱问一下，第N大元素不应该是从后数第N个吗？inorder访问的第N个是从头数N个阿。
|
m******9
发帖数: 968 | 16 祝福，谢谢你的提醒，楼主，bst里面有重复的数确实容易忽略， |
H*M
发帖数: 1268 | 17 u can change the inorder "order", from right, itself, to the left
【在 r****o 的大作中提到】
: You are right
|
r*********l
发帖数: 170 | |
m*****k
发帖数: 64 | 19 DAMN, 被拒了。可真够快的，估计是没考虑duplication. |
k***e
发帖数: 556 | 20 how did you know it is because you did not consider duplicate?
Did you ask him whether that is a balanced tree with the extra information
at each node that records the number of nodes in the subtree rooted at it?
【在 m*****k 的大作中提到】
: DAMN, 被拒了。可真够快的，估计是没考虑duplication.
|
|
|
m*****k
发帖数: 64 | 21 恩？我没太明白为什么要是balanced bst?
information
it?
【在 k***e 的大作中提到】
: how did you know it is because you did not consider duplicate?
: Did you ask him whether that is a balanced tree with the extra information
: at each node that records the number of nodes in the subtree rooted at it?
|
k***e
发帖数: 556 | 22 if it is rb balanced or AVL balanced, we can make sure to find the i-th
largest
in lgn time.
i guess he wants you to mention this.
【在 m*****k 的大作中提到】
: 恩？我没太明白为什么要是balanced bst?
:
: information
: it?
|
h*********e
发帖数: 56 | 23 和重复没关系。Tree size N, find M-th biggest, 你的算法O(N)，有O(lgN)算法。 |
m*****k
发帖数: 64 | 24 请问您能给个算法么？怎么做到O(lgN)
【在 h*********e 的大作中提到】
: 和重复没关系。Tree size N, find M-th biggest, 你的算法O(N)，有O(lgN)算法。
|
d******a
发帖数: 238 | 25 I don't think you could find a solution of O(lgn) for this problem in the
worst case. when a BST is similar to a linked list, you need O(n) time
【在 h*********e 的大作中提到】
: 和重复没关系。Tree size N, find M-th biggest, 你的算法O(N)，有O(lgN)算法。
|
m*****k
发帖数: 64 | 26 你是说，如果知道at each node that records the number of nodes in the subtree
rooted at it. 那么，可以根据number of nodes in left and right subtrees,来找?
比如说left subtree has 3 nodes, right subtree has 3nodes, and we want to
find the 6th biggest node, then it should be on left subtree,then
recursively find it? so it is o( lgn). Is it what you are talking about?
information
it?
【在 k***e 的大作中提到】
: how did you know it is because you did not consider duplicate?
: Did you ask him whether that is a balanced tree with the extra information
: at each node that records the number of nodes in the subtree rooted at it?
|
b***e
发帖数: 1419 | 27 没必要. 即使是按值求第n个, 也只需要一个整数index来记住当前的数是第几个. 无需
数组.
【在 r****o 的大作中提到】
: 那就再存一个数组，把前几个元素保存下来，就可以知道非重复的第N大元素了把
: BTW，3rd larget 应该是3把?
|
h*********e
发帖数: 56 | 28 我来试试。
struct Node {
....int nSmaller;....//total number of node in its left subtree
....Node *left, *right;
};
//select m-th in the sorted order, starting with zero
Node* select(Node* root, int m) {
....if(root==NULL)
........return NULL;
....if(root->nSmaller == m)
........return root;
....if(root->nSmaller < m)
........return select(root->right, m-nSmaller);
....else
........return select(root->left, m);
}
最好嵌入到balanced BST中，以保证O(lgN),比如AVL， red-black tree. |
m*****k
发帖数: 64 | 29 这是基于知道 nSmaller 左子树结点个数。
【在 h*********e 的大作中提到】
: 我来试试。
: struct Node {
: ....int nSmaller;....//total number of node in its left subtree
: ....Node *left, *right;
: };
: //select m-th in the sorted order, starting with zero
: Node* select(Node* root, int m) {
: ....if(root==NULL)
: ........return NULL;
: ....if(root->nSmaller == m)
|
h*********e
发帖数: 56 | 30 你可以在插入的时候更新这个信息啊。
if (root->key > newkey) {
....root->nSmall++;
....insert(root->left, newkey);
} else {
....insert(root->right, newkey);
}
【在 m*****k 的大作中提到】
: 这是基于知道 nSmaller 左子树结点个数。
|
