unidentified_title - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>paladin - 谈古论金，黄梁一梦

unidentified_title

unidentified_title# paladin - 谈古论金，黄梁一梦

m*k2095-12-31 08:12

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 谢谢！

e*d2095-12-31 08:12

2 楼

有没有相关模板，还是必须我们自己找律师搞了？
多谢指点。

u*r2095-12-31 08:12

3 楼

发信人： Damieon(快乐大男孩), 信区： paladin
标题：宝玉身边有个心肠歹毒的丫鬟，她是谁？
发信站： BBS未名空间站(Mon Oct 23 11:29:23 2017,GMT)
袭人出身低微，但心志不低，又有在怡红院里离宝玉最贴身的便利，总想着有朝一日能
从下人一跃成为怡红院主子的念头。且与宝玉有“初试雲雨”之亲，更觉得自己的梦想
终会成真的。
再者，袭人虽为下人，但凭着她的聪明伶俐和忍辱负重的志向，表面上处处表现出和气
待人不与人争长短的姿态，左右逢缘，故赢得了老太太、贾宝玉和众夫人的宠爱，在怡
红院里占稳了众丫鬟之首的位置，就是到了别处他人也不敢小瞧了她！
然而背地里，她却时时刻刻为巩固和确保自己的地位费尽了心机，真可谓是不择手段。
她最嫉妒林黛玉的美丽、才学，薛宝钗的高贵、大气，视她们俩人为竞争对手，以排除
和取缔她们在宝玉心中地位为目标，但表面上又对她们俩极尽阿谀奉承，真是居心可诛。
然袭人机关算尽，终还是美梦破灭，没能逃脱自己为下人的命运。

H*M2095-12-31 08:12

4 楼

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 谢谢！

a*g2095-12-31 08:12

5 楼

自己搞，很容易的。就是——
转换身份的申请表格
自己的合法身份（护照、以前身份历史）
配偶的合法身份（护照、工作证明）
以及二人的婚姻关系。
另外可能还需要财产证明。
移民局给你发收据，你就不算滞留了。

【在 e****d 的大作中提到】

: 有没有相关模板，还是必须我们自己找律师搞了？
: 多谢指点。

y*r2095-12-31 08:12

6 楼

我感觉你误解袭人了！她非常清楚自己的地位，所以她不可能和林黛玉，薛宝钗争第一
的，甚至都不敢争第二，毕竟他的出生在那里，而贾府等级制度（家庭出身）非常森严
，她不太可能来挑战所有的人，估计她也就把自己定位成赵姨娘。即使地位上不高，但
是天天在名誉上最高主人（贾政）身边，就算打个小报告，也够其他人享受了。
最后离开贾府时，对后事的安排还是想当清楚明了的！

r*o2095-12-31 08:12

7 楼

怎么找N-th largest elelment in BST?
我想的是用in-order travel，然后找第N个Visit的元素。这种方法可以吗？
还有更好的方法吗？

element

【在 m*****k 的大作中提到】

r*o2095-12-31 08:12

8 楼

弱问，front-end到底是干嘛的啊?

【在 H*M 的大作中提到】

: bless louzhu!
:
: element

m*k2095-12-31 08:12

9 楼

其实我就是用这个方法的，但是如果有重复的值就不灵了吧，比如1,2,2,2,3 3rd
largest 是 1

【在 r****o 的大作中提到】

: 怎么找N-th largest elelment in BST?
: 我想的是用in-order travel，然后找第N个Visit的元素。这种方法可以吗？
: 还有更好的方法吗？
:
: element

m*k2095-12-31 08:12

10 楼

比如说 Google Map, Gmail 的前台Ajax。

【在 r****o 的大作中提到】

: 弱问，front-end到底是干嘛的啊?

r*o2095-12-31 08:12

11 楼

那就再存一个数组，把前几个元素保存下来，就可以知道非重复的第N大元素了把
BTW，3rd larget 应该是3把?

【在 m*****k 的大作中提到】

: 其实我就是用这个方法的，但是如果有重复的值就不灵了吧，比如1,2,2,2,3 3rd
: largest 是 1

m*k2095-12-31 08:12

12 楼

我的理解是 1st largest is 3, 2nd largest is 2, 3rd largest is 1。

【在 r****o 的大作中提到】

: 那就再存一个数组，把前几个元素保存下来，就可以知道非重复的第N大元素了把
: BTW，3rd larget 应该是3把?

r*o2095-12-31 08:12

13 楼

呵呵，不好意思我看错了。

【在 m*****k 的大作中提到】

: 我的理解是 1st largest is 3, 2nd largest is 2, 3rd largest is 1。

g*y2095-12-31 08:12

14 楼

顺序统计量并没要求要严格的greater than吧？只要是排序后的第N个就行了吧
我觉得lz不用担心这个啦~

【在 m*****k 的大作中提到】

: 我的理解是 1st largest is 3, 2nd largest is 2, 3rd largest is 1。

m*k2095-12-31 08:12

15 楼

不知道啊，觉得好心虚啊！

【在 g*******y 的大作中提到】

: 顺序统计量并没要求要严格的greater than吧？只要是排序后的第N个就行了吧
: 我觉得lz不用担心这个啦~

z*32095-12-31 08:12

16 楼

我也觉得不用担心有重复的问题
bless

【在 m*****k 的大作中提到】

: 不知道啊，觉得好心虚啊！

m*k2095-12-31 08:12

17 楼

谢谢你们！

【在 z*********3 的大作中提到】

: 我也觉得不用担心有重复的问题
: bless

c*o2095-12-31 08:12

18 楼

弱问一下，第N大元素不应该是从后数第N个吗？inorder访问的第N个是从头数N个阿。

r*o2095-12-31 08:12

19 楼

You are right

【在 c*****o 的大作中提到】

: 弱问一下，第N大元素不应该是从后数第N个吗？inorder访问的第N个是从头数N个阿。

m*92095-12-31 08:12

20 楼

祝福，谢谢你的提醒，楼主，bst里面有重复的数确实容易忽略，

H*M2095-12-31 08:12

21 楼

u can change the inorder "order", from right, itself, to the left

【在 r****o 的大作中提到】

: You are right

r*l2095-12-31 08:12

22 楼

楼上的头像真是与时俱进

m*k2095-12-31 08:12

23 楼

DAMN, 被拒了。可真够快的，估计是没考虑duplication.

k*e2095-12-31 08:12

24 楼

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*k2095-12-31 08:12

25 楼

恩？我没太明白为什么要是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*e2095-12-31 08:12

26 楼

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*e2095-12-31 08:12

27 楼

和重复没关系。Tree size N, find M-th biggest, 你的算法O(N)，有O(lgN)算法。

m*k2095-12-31 08:12

28 楼

请问您能给个算法么？怎么做到O(lgN)

【在 h*********e 的大作中提到】

: 和重复没关系。Tree size N, find M-th biggest, 你的算法O(N)，有O(lgN)算法。

d*a2095-12-31 08:12

29 楼

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*k2095-12-31 08:12

30 楼

你是说，如果知道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 的大作中提到】

b*e2095-12-31 08:12

31 楼

没必要. 即使是按值求第n个, 也只需要一个整数index来记住当前的数是第几个. 无需
数组.

【在 r****o 的大作中提到】

: 那就再存一个数组，把前几个元素保存下来，就可以知道非重复的第N大元素了把
: BTW，3rd larget 应该是3把?

h*e2095-12-31 08:12

32 楼

我来试试。
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*k2095-12-31 08:12

33 楼

这是基于知道 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*e2095-12-31 08:12

34 楼

你可以在插入的时候更新这个信息啊。
if (root->key > newkey) {
....root->nSmall++;
....insert(root->left, newkey);
} else {
....insert(root->right, newkey);
}

【在 m*****k 的大作中提到】

: 这是基于知道 nSmaller 左子树结点个数。