外行们少说两句吧，尤其本身不搞病毒的 - 未名空间MITBBS历史存档

外行们少说两句吧，尤其本身不搞病毒的# Biology - 生物学

d*g2012-11-24 08:11

1 楼

1. Numbers are generated randomly and passed to a method. Write a program to find the median value as new numbers are generated.
I told the interviewer about the method using two heaps. He doesn't like it (said it could be simpler), and asked for another way to do it. I gave up...
2. Find the median value for an array of values (without sorting it)
Thank you for your insights!

c*x2012-11-24 08:11

2 楼

大大包子求， $200最好

y*u2012-11-24 08:11

3 楼

人家靠连续几年每天工作12小时拼出来的成果，你个外行扫一眼paper，轻轻松松两句
话就能给否了？有这本事还用做千老？要尊重别人。
如果看完一篇paper，什么都没学到，尽挑刺了，那你浪费时间看它干嘛。人家发都发
了，你挑出了100个刺又有什么用。

g*s2012-11-24 08:11

4 楼

program to find the median value as new numbers are generated.
it (said it could be simpler), and asked for another way to do it. I gave
up...
Do you mean you will have a randomly generated integer stream and you need
to update the median dynamically along the stream? How does your 2-heap
solution work?

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

: 1. Numbers are generated randomly and passed to a method. Write a program to find the median value as new numbers are generated.
: I told the interviewer about the method using two heaps. He doesn't like it (said it could be simpler), and asked for another way to do it. I gave up...
: 2. Find the median value for an array of values (without sorting it)
: Thank you for your insights!

g*x2012-11-24 08:11

5 楼

$200的包子是求不到的
自己去ebay吧

t*s2012-11-24 08:11

6 楼

科学是不怕人挑刺的，
发文章就不是给人指路或让人挑刺吗

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

: 人家靠连续几年每天工作12小时拼出来的成果，你个外行扫一眼paper，轻轻松松两句
: 话就能给否了？有这本事还用做千老？要尊重别人。
: 如果看完一篇paper，什么都没学到，尽挑刺了，那你浪费时间看它干嘛。人家发都发
: 了，你挑出了100个刺又有什么用。

h*n2012-11-24 08:11

7 楼

according to your description, I think the solution of using two heaps would
be:
maintain a min-heap & a max-heap, which satisfying that
1) all numbers in min-heap are larger or equal than that of max-heap
2) the difference of the numbers in two heaps should be no more than 1, depe
nding on that the total number of numbers is odd or even
with the above property, the median can be easily derived from top elements
on heap(s)
therefore, the algorithm is designed to maintain the above two properties:
1) whenever there is a new number generated, insert that number to proper he
ap, say if the number is larger than the top element of min-heap, it is inse
rted to the min-heap; or if the number is less than the top element of max-h
eap, it is inserted to the max-heap
2) then calculate the number of numbers of those two heaps, if the number of
one heap is larger than that of the other heap, extract the top element of
the heap with more numbers and then insert that to the heap with less number
s
3) calculate the median
-if numbers in two heaps are equal, the median = average of the top elements
of two heaps
-if numbers in two heaps are not equal , the median = the top element of the
heap with more numbers
another solution would be order-statistic tree, an augmented data structure
from red-black tree where each node x store the number of node in the subtre
e rooted at node x (refer to CLRS chap 14), however, I do not think it is pr
oper to code over the phone
any other simpler solution?

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

:
: program to find the median value as new numbers are generated.
: it (said it could be simpler), and asked for another way to do it. I gave
: up...
: Do you mean you will have a randomly generated integer stream and you need
: to update the median dynamically along the stream? How does your 2-heap
: solution work?

g*92012-11-24 08:11

8 楼

我有一个150的，需要的话PM

d*j2012-11-24 08:11

9 楼

主要是一开始外行说的做的太多了.
李博士的研究重要性肯定是有的.
可是
外行晓东,非要让人在文章还没发表之前(当时已被CNS据,那可是内行评的啊),就得什么
周光召奖;
外行饶毅,把人的结果非要和体制联系起来;
还有ELIFE请的评价的晓东的友人,算半个外行吧.
这事儿,WSN在这儿挑点刺,根本无所谓.如果只是一片文章的话,WSN们根本不会在这儿吵
吵.
可恶的是为了自己利益炒作的外行和刚把人据掉,又出来猛夸的内行.

h*n2012-11-24 08:11

10 楼

a simpler solution should be just use 2)'s solution to answer 1)
i think the interview tries to make the thing simple, we think too complicat
e, maybe two heap solution is good for sliding window of numbers

to find the median value as new numbers are generated.
it (said it could be simpler), and asked for another way to do it. I gave up
...

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

: 1. Numbers are generated randomly and passed to a method. Write a program to find the median value as new numbers are generated.
: I told the interviewer about the method using two heaps. He doesn't like it (said it could be simpler), and asked for another way to do it. I gave up...
: 2. Find the median value for an array of values (without sorting it)
: Thank you for your insights!

j*22012-11-24 08:11

11 楼

我想要150的，可以送我吗？非常感谢！！！最好不需要DD的。

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

: 我有一个150的，需要的话PM

S*s2012-11-24 08:11

12 楼

从你的发帖来看，你还是一个比较fair的人。
问题是
1）你不了解NIBS的处境和在中国真正做science的艰难。
2）饶毅为什么要这么做
3）Elife的审稿机制
4）既然你都意识到“可恶的是为了自己利益炒作的外行和刚把人据掉,又出来猛夸的内
行”，你就更应该理解李博士的处境。

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

: 主要是一开始外行说的做的太多了.
: 李博士的研究重要性肯定是有的.
: 可是
: 外行晓东,非要让人在文章还没发表之前(当时已被CNS据,那可是内行评的啊),就得什么
: 周光召奖;
: 外行饶毅,把人的结果非要和体制联系起来;
: 还有ELIFE请的评价的晓东的友人,算半个外行吧.
: 这事儿,WSN在这儿挑点刺,根本无所谓.如果只是一片文章的话,WSN们根本不会在这儿吵
: 吵.
: 可恶的是为了自己利益炒作的外行和刚把人据掉,又出来猛夸的内行.

b*e2012-11-24 08:11

13 楼

1. build a binary search tree. Node contains the size of the tree under it.
O(log(n)) average. (Since input is random, depth should be O(log(n))
expected.
2. quick select is one way. O(N) average, O(N^2) worst case. Or build BST;
use a heap, etc

to find the median value as new numbers are generated.
it (said it could be simpler), and asked for another way to do it. I gave up
...

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

: 1. Numbers are generated randomly and passed to a method. Write a program to find the median value as new numbers are generated.
: I told the interviewer about the method using two heaps. He doesn't like it (said it could be simpler), and asked for another way to do it. I gave up...
: 2. Find the median value for an array of values (without sorting it)
: Thank you for your insights!

h*e2012-11-24 08:11

14 楼

i have a $150, no dd, pm if you want.

n*y2012-11-24 08:11

15 楼

听着和薄起来的瓜瓜没贪污+温影帝的仰望星空一样动听

【在 S*********s 的大作中提到】

: 从你的发帖来看，你还是一个比较fair的人。
: 问题是
: 1）你不了解NIBS的处境和在中国真正做science的艰难。
: 2）饶毅为什么要这么做
: 3）Elife的审稿机制
: 4）既然你都意识到“可恶的是为了自己利益炒作的外行和刚把人据掉,又出来猛夸的内
: 行”，你就更应该理解李博士的处境。

y*i2012-11-24 08:11

16 楼

http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on

r*s2012-11-24 08:11

17 楼

冒昧问一下什么是DD？

【在 j*****2 的大作中提到】

: 我想要150的，可以送我吗？非常感谢！！！最好不需要DD的。

n*y2012-11-24 08:11

18 楼

你怎么知道---"和刚把人据掉,又出来猛夸的内行." ?

【在 S*********s 的大作中提到】

: 从你的发帖来看，你还是一个比较fair的人。
: 问题是
: 1）你不了解NIBS的处境和在中国真正做science的艰难。
: 2）饶毅为什么要这么做
: 3）Elife的审稿机制
: 4）既然你都意识到“可恶的是为了自己利益炒作的外行和刚把人据掉,又出来猛夸的内
: 行”，你就更应该理解李博士的处境。

g*s2012-11-24 08:11

19 楼

i think the 2-heap solutions is just sigma(O(lgK)) which implies O(NlgN)?
However, linear selection is sigma(O(K)) i.e. O(N^2).

complicat
gave up

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

: a simpler solution should be just use 2)'s solution to answer 1)
: i think the interview tries to make the thing simple, we think too complicat
: e, maybe two heap solution is good for sliding window of numbers
:
: to find the median value as new numbers are generated.
: it (said it could be simpler), and asked for another way to do it. I gave up
: ...

Y*92012-11-24 08:11

20 楼

我有$150的，不需要direct deposit.

d*j2012-11-24 08:11

21 楼

李博士的成绩与NIBS只有一点毛的关系；与NIBS的处境和中国做SCIENCE没有半毛关系(
NIBS相关人员已进入973总顾问组和专项专家组，去年在非正常申请时段获得4项3千万
的973，看来处境非常的好）；
饶毅为啥这么做，让很多人反感，只能问他自己了；
ELIFE是新杂志，审稿机制还没有成制度化，现在说成是CNS级别的杂志，为时尚早。
李博士是身不由己了；要挺住。

【在 S*********s 的大作中提到】

: 从你的发帖来看，你还是一个比较fair的人。
: 问题是
: 1）你不了解NIBS的处境和在中国真正做science的艰难。
: 2）饶毅为什么要这么做
: 3）Elife的审稿机制
: 4）既然你都意识到“可恶的是为了自己利益炒作的外行和刚把人据掉,又出来猛夸的内
: 行”，你就更应该理解李博士的处境。

d*g2012-11-24 08:11

22 楼

Nice description of the two heap method. This is exactly what i told the
interviewer, although he is not big fan of it:(
He suggested it's not necessary to keep the order of all numbers (which is
what the two heap method is doing). One should be able to update the median
using the info from the previous selection, when a new number arrives.
BTW, he used the example of computing the moving average of an array of
numbers as a hint: When calculate moving average of the next n consecutive
numbers, you want to reuse the previous computed moving average. Just
multiply that average by m, minus first number and add a new number, then
divide by m again.
However I don't see how to incorporate this idea into our solution.

complicat
up

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

: a simpler solution should be just use 2)'s solution to answer 1)
: i think the interview tries to make the thing simple, we think too complicat
: e, maybe two heap solution is good for sliding window of numbers
:
: to find the median value as new numbers are generated.
: it (said it could be simpler), and asked for another way to do it. I gave up
: ...

j*x2012-11-24 08:11

23 楼

我觉得你还是做好你自己的事情吧，如果你不是当事人之一，最好不要在这里瞎搅混水
，妄谈science之外的事情，既不能代表当事人的真实想法，更会带来外界的猜疑和误
会。

系(

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

: 李博士的成绩与NIBS只有一点毛的关系；与NIBS的处境和中国做SCIENCE没有半毛关系(
: NIBS相关人员已进入973总顾问组和专项专家组，去年在非正常申请时段获得4项3千万
: 的973，看来处境非常的好）；
: 饶毅为啥这么做，让很多人反感，只能问他自己了；
: ELIFE是新杂志，审稿机制还没有成制度化，现在说成是CNS级别的杂志，为时尚早。
: 李博士是身不由己了；要挺住。

l*r2012-11-24 08:11

24 楼

是不是可以这么做：
1. creat a binary search tree. When a new item comes, insert into the tree。
O(logN)
2. To get the new medium, check if the newly generated value is bigger or
smaller than the previous medium.
- if bigger: the right child of the old medium is the new medium (if null,
then parent)
- if smaller: the left child of the old medium (if null, then parent)
如果偶数个数medium定义成中间两个的mean的话，需要两个指针对应奇偶数的情况，做
法还是跟上面类似。
O(1)
Overall O(logN)

median

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

: Nice description of the two heap method. This is exactly what i told the
: interviewer, although he is not big fan of it:(
: He suggested it's not necessary to keep the order of all numbers (which is
: what the two heap method is doing). One should be able to update the median
: using the info from the previous selection, when a new number arrives.
: BTW, he used the example of computing the moving average of an array of
: numbers as a hint: When calculate moving average of the next n consecutive
: numbers, you want to reuse the previous computed moving average. Just
: multiply that average by m, minus first number and add a new number, then
: divide by m again.

d*j2012-11-24 08:11

25 楼

呵呵。谁代表人家当事人的真实想法了？
共勉。

【在 j****x 的大作中提到】

: 我觉得你还是做好你自己的事情吧，如果你不是当事人之一，最好不要在这里瞎搅混水
: ，妄谈science之外的事情，既不能代表当事人的真实想法，更会带来外界的猜疑和误
: 会。
:
: 系(

g*s2012-11-24 08:11

26 楼

it's been proposed by others to use order statistic tree, i.e., a
balanced bst augmented with size of sub-tree.
this is a classical data structure and most likely the expected answer
by the interviewer. it is easier to understand and stronger in sense of
picking up any n-th element in O(lgN). the complexity is the same as ur
solution though.
ur solution is still interesting to read.

the
(which is
median
of
consecutive
then

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

: Nice description of the two heap method. This is exactly what i told the
: interviewer, although he is not big fan of it:(
: He suggested it's not necessary to keep the order of all numbers (which is
: what the two heap method is doing). One should be able to update the median
: using the info from the previous selection, when a new number arrives.
: BTW, he used the example of computing the moving average of an array of
: numbers as a hint: When calculate moving average of the next n consecutive
: numbers, you want to reuse the previous computed moving average. Just
: multiply that average by m, minus first number and add a new number, then
: divide by m again.

d*j2012-11-24 08:11

27 楼

另外，谢谢了。你自己好好玩吧。
这是关于乙肝受体的最后一贴。

h*n2012-11-24 08:11

28 楼

I kind of see his hint, the main point to use of the previous result
suppose you use the select algorithm to find the medium, when the next new n
umber comes, you could put it on either the left or right, depending on how
many numbers on each side, you can use select algorithm on the proper part f
or the new medium of the set of numbers

median

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

: Nice description of the two heap method. This is exactly what i told the
: interviewer, although he is not big fan of it:(
: He suggested it's not necessary to keep the order of all numbers (which is
: what the two heap method is doing). One should be able to update the median
: using the info from the previous selection, when a new number arrives.
: BTW, he used the example of computing the moving average of an array of
: numbers as a hint: When calculate moving average of the next n consecutive
: numbers, you want to reuse the previous computed moving average. Just
: multiply that average by m, minus first number and add a new number, then
: divide by m again.

j*x2012-11-24 08:11

29 楼

那就请不要刻意的或有意无意的以当事人/当事人代言人的身份自我带入了，其实之前
我开玩笑说你是不是李博士本人的时候就已经算是提醒了。之前你以“知情人”角度所
做的无关science本身的评论，我个人认为如果不是直接当事人，说出来非常不合适。
摆正自己的位置，不负责任的话少说，这个要求不高吧，与你共勉

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

: 呵呵。谁代表人家当事人的真实想法了？
: 共勉。

d*g2012-11-24 08:11

30 楼

I guess you are right. But this is O(N) complexity rather than O(logN) by
using the max and min heap method.

n
how
f

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

: I kind of see his hint, the main point to use of the previous result
: suppose you use the select algorithm to find the medium, when the next new n
: umber comes, you could put it on either the left or right, depending on how
: many numbers on each side, you can use select algorithm on the proper part f
: or the new medium of the set of numbers
:
: median

d*j2012-11-24 08:11

31 楼

晕倒，你还没完了。
要不是你自己声称替李博士圆场，我也不会接你的话茬的。
同学，作为业内人士，摆正自己的位置，不负责任的话少说，这个要求不高吧，与你共勉

【在 j****x 的大作中提到】

: 那就请不要刻意的或有意无意的以当事人/当事人代言人的身份自我带入了，其实之前
: 我开玩笑说你是不是李博士本人的时候就已经算是提醒了。之前你以“知情人”角度所
: 做的无关science本身的评论，我个人认为如果不是直接当事人，说出来非常不合适。
: 摆正自己的位置，不负责任的话少说，这个要求不高吧，与你共勉

J*a2012-11-24 08:11

32 楼

he is looking for using randomized quicksort. (not full sort, just use the
partition routine)
just use inplace quicksort, use the new value as pivot value and while the
final placement is not in the middle, call the partition routine on the
larger portion.
This should be as fast as the heap method, but no additional space needed.
For more information you can watch MIT opencourse for algorithm
Lecture 4: Quicksort, Randomized Algorithms
and
Lecture 6: Order Statistics, Median

median

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

: Nice description of the two heap method. This is exactly what i told the
: interviewer, although he is not big fan of it:(
: He suggested it's not necessary to keep the order of all numbers (which is
: what the two heap method is doing). One should be able to update the median
: using the info from the previous selection, when a new number arrives.
: BTW, he used the example of computing the moving average of an array of
: numbers as a hint: When calculate moving average of the next n consecutive
: numbers, you want to reuse the previous computed moving average. Just
: multiply that average by m, minus first number and add a new number, then
: divide by m again.

j*x2012-11-24 08:11

33 楼

我以一个相关研究人员，和当事人没有任何瓜葛，不预带个人偏见和立场，仅从学术的
角度来解释网上这些质合理的不合理的疑，因为李博士本人显然没有来BBS上答疑，所
以开玩笑说这是在替李博士圆场，敢问哪里不负责任了？
敢问你又是以什么身份在说那些话呢？什么被逼无奈，什么身不由己，什么不想再烦了
，请问你摆的是什么位置，负的又是什么责任？

共勉

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

: 晕倒，你还没完了。
: 要不是你自己声称替李博士圆场，我也不会接你的话茬的。
: 同学，作为业内人士，摆正自己的位置，不负责任的话少说，这个要求不高吧，与你共勉

u*e2012-11-24 08:11

34 楼

for the first problem
my idea is to simply use an ordered linked list with both next and prev poin
t on each node.
Remember the pointer to the current median value and the size of the list. w
henever there is a new value, just put the new value to correct position in
the list(search can start from current median value) and move the median val
ue point one next or prev depending on the size of the list and the position
of new value.

would
depe
elements
he

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

: according to your description, I think the solution of using two heaps would
: be:
: maintain a min-heap & a max-heap, which satisfying that
: 1) all numbers in min-heap are larger or equal than that of max-heap
: 2) the difference of the numbers in two heaps should be no more than 1, depe
: nding on that the total number of numbers is odd or even
: with the above property, the median can be easily derived from top elements
: on heap(s)
: therefore, the algorithm is designed to maintain the above two properties:
: 1) whenever there is a new number generated, insert that number to proper he

d*j2012-11-24 08:11

35 楼

同学，要以事实说话，在你所谓的玩笑之前，我对你的评论一直是以科学的态度支持的。
准许你业内人士开玩笑，就不许我业外人士开玩笑？
你说人走穴；你还要给圆场。我认为作为业内人士，即使是开玩笑，也是很不负责的。

【在 j****x 的大作中提到】

: 我以一个相关研究人员，和当事人没有任何瓜葛，不预带个人偏见和立场，仅从学术的
: 角度来解释网上这些质合理的不合理的疑，因为李博士本人显然没有来BBS上答疑，所
: 以开玩笑说这是在替李博士圆场，敢问哪里不负责任了？
: 敢问你又是以什么身份在说那些话呢？什么被逼无奈，什么身不由己，什么不想再烦了
: ，请问你摆的是什么位置，负的又是什么责任？
:
: 共勉

y*i2012-11-24 08:11

36 楼

我的想法和你的有类似的地方。
首先你这里有一个地方是不是错了：如果新的随机数数比旧的中位数大，旧的右孩子(
right child)不应该是新的中位数，应该是旧的后继(successor)，这样才是旧的中位
数的右子树的最小值。
你这个的确能达到O(logN)，不过需要额外O(N)空间，对吧？我的想法是in place用
quick sort的random partition部分，用旧的中位数作为轴，同样假设新的随机数比旧
的中位数大，那么轴右边的较大部分的数加上新的随机数用普通的选择最小值的方法选
出的最小值就应该是新的中位数，时间O(N)，空间O(1)。

。

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

: 是不是可以这么做：
: 1. creat a binary search tree. When a new item comes, insert into the tree。
: O(logN)
: 2. To get the new medium, check if the newly generated value is bigger or
: smaller than the previous medium.
: - if bigger: the right child of the old medium is the new medium (if null,
: then parent)
: - if smaller: the left child of the old medium (if null, then parent)
: 如果偶数个数medium定义成中间两个的mean的话，需要两个指针对应奇偶数的情况，做
: 法还是跟上面类似。

j*x2012-11-24 08:11

37 楼

我已经以事实为基础解释清楚了，李博士最近在不同的场合的各种报告非常多，所以才
有“走穴”这一玩笑，现在已经不是什么八十年代了同学，走穴早就不能算是贬义词了
。我也说了，好的科学和好的科学家都需要宣传，这根本没什么问题。至于所谓圆场，
意思更加明显，满版的质疑之声靠谱的不靠谱的鱼龙混杂，但是从科学角度的真正的解
释这些质疑的声音很弱。李博士自然不会来此答疑，我从业内研究人员的角度解释李博
士的新结果新发现，应对这里的质疑之声，开个玩笑说“圆场”，很过分吗？请问哪里
不负责任了。好吧，如果比如你这类非当事人觉得很过分，那我之前也道歉过了，有则
改之无则加勉，OK的。
可是你呢？作为业外人士，玩笑当然没问题，冷嘲热讽都合情合理，但是不是当事人却
刻意的以当事人的口吻，揭示所谓内幕消息，挑起无关的矛盾，这就不是最后一句开玩
笑可以解释了吧？我可以为我说的这些玩笑负责，你能为你说的这些所谓内幕负责吗？

的。

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

: 同学，要以事实说话，在你所谓的玩笑之前，我对你的评论一直是以科学的态度支持的。
: 准许你业内人士开玩笑，就不许我业外人士开玩笑？
: 你说人走穴；你还要给圆场。我认为作为业内人士，即使是开玩笑，也是很不负责的。

l*i2012-11-24 08:11

38 楼

我觉得第一题不需要建立所有数的数据结构，其实只需要记录当前median，median的
sucessor和predecessor，每次来一个新数的时候，新的median只可能是那三个数中的
一个，每次根据大小情况以及目前总数奇偶update那三个数就可以了。

D*a2012-11-24 08:11

39 楼

到底哪个是你最后一帖啊

的。

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

: 同学，要以事实说话，在你所谓的玩笑之前，我对你的评论一直是以科学的态度支持的。
: 准许你业内人士开玩笑，就不许我业外人士开玩笑？
: 你说人走穴；你还要给圆场。我认为作为业内人士，即使是开玩笑，也是很不负责的。

l*32012-11-24 08:11

40 楼

我想可以这样做：
1）
定义一个堆栈类，push(),pop(),size(),max/min()。以上操作都可以在O(1)完成
维持两个堆栈，一个max栈，一个min栈。max栈中记录所有比median小的数，min栈中记录所有比median大的数。
接受新数时，决定插入max栈或是min栈，如果max和min栈不平衡，rebalance，pop多的栈，作为新median，将老median插入少的栈中。
每个元素都可以在O(1)时间内完成操作。
2）
输入数组，一次调用第一题中的方法，时间复杂度O(n)。

to find the median value as new numbers are generated.
it (said it could be simpler), and asked for another way to do it. I gave up
...

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

: 1. Numbers are generated randomly and passed to a method. Write a program to find the median value as new numbers are generated.
: I told the interviewer about the method using two heaps. He doesn't like it (said it could be simpler), and asked for another way to do it. I gave up...
: 2. Find the median value for an array of values (without sorting it)
: Thank you for your insights!

j*x2012-11-24 08:11

41 楼

他是被我激出来的，后面的帖子不算数的，呵呵
你来给我评评理，我开的那个玩笑到底过分不？啥时候BBS上也这么敏感了

【在 D*a 的大作中提到】

: 到底哪个是你最后一帖啊
:
: 的。

c*m2012-11-24 08:11

42 楼

这个题目就是online median selection, 我觉得two priority queues (min-heap &
max-heap)应该是目前比较理想的办法了，而且也好理解。
hopen的解释很详细了。
对于题目二，如果单纯一次性找到一个array的mean，并且不用sorting的话，可以用
kth element selection method。但这方法又不能用在data stream上。
面试官的提示很奇怪呀，莫非他只是让你找mean，而不是median？
Anyway, bless~~

d*j2012-11-24 08:11

43 楼

朵啊同学，没办法啊，人追着我问啊。

【在 D*a 的大作中提到】

: 到底哪个是你最后一帖啊
:
: 的。

z*o2012-11-24 08:11

44 楼

这个很明显不对啊. 一个反例: 5 6 7 8 9 4 3 2 1 0

【在 l**i 的大作中提到】

: 我觉得第一题不需要建立所有数的数据结构，其实只需要记录当前median，median的
: sucessor和predecessor，每次来一个新数的时候，新的median只可能是那三个数中的
: 一个，每次根据大小情况以及目前总数奇偶update那三个数就可以了。

d*j2012-11-24 08:11

45 楼

呵呵，我是敏感了，你不觉得你也是吗？

【在 j****x 的大作中提到】

: 他是被我激出来的，后面的帖子不算数的，呵呵
: 你来给我评评理，我开的那个玩笑到底过分不？啥时候BBS上也这么敏感了

z*o2012-11-24 08:11

46 楼

1的堆栈是无序的, pop多的那个出来的东西不一定是新的median

栈中记录所有比median大的
数。
pop多的栈，作为新median，将
老median插入少的栈中。
up

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

: 我想可以这样做：
: 1）
: 定义一个堆栈类，push(),pop(),size(),max/min()。以上操作都可以在O(1)完成
: 维持两个堆栈，一个max栈，一个min栈。max栈中记录所有比median小的数，min栈中记录所有比median大的数。
: 接受新数时，决定插入max栈或是min栈，如果max和min栈不平衡，rebalance，pop多的栈，作为新median，将老median插入少的栈中。
: 每个元素都可以在O(1)时间内完成操作。
: 2）
: 输入数组，一次调用第一题中的方法，时间复杂度O(n)。
:
: to find the median value as new numbers are generated.

d*j2012-11-24 08:11

47 楼

同学,你看看,这里面认为我是或者是冒充是李博士代言人的除了你,没有几个人吧.
我认为对目前的炒作,被逼无奈,身不由己,不想再烦了,是作为一个对科研执着追求热爱
的的人(象李博士这样的)合理反应.
你说我说的内幕,其实绝大多数是事实吧,比如这贴里的
外行晓东,非要让人在文章还没发表之前(当时已被CNS据,那可是内行评的啊),就得什么
周光召奖;
外行饶毅,把人的结果非要和体制联系起来;
还有ELIFE请的评价的晓东的友人,算半个外行吧.
NIBS相关人员已进入973总顾问组和专项专家组，去年在非正常申请时段获得4项3千万
的973，看来处境非常的好
ELIFE是新杂志，审稿机制还没有成制度化，现在说成是CNS级别的杂志，为时尚早。
当然会有小部分有出入，但谁又会全对啊。
我还说过，你心肠挺好。节日快乐。

【在 j****x 的大作中提到】

: 我已经以事实为基础解释清楚了，李博士最近在不同的场合的各种报告非常多，所以才
: 有“走穴”这一玩笑，现在已经不是什么八十年代了同学，走穴早就不能算是贬义词了
: 。我也说了，好的科学和好的科学家都需要宣传，这根本没什么问题。至于所谓圆场，
: 意思更加明显，满版的质疑之声靠谱的不靠谱的鱼龙混杂，但是从科学角度的真正的解
: 释这些质疑的声音很弱。李博士自然不会来此答疑，我从业内研究人员的角度解释李博
: 士的新结果新发现，应对这里的质疑之声，开个玩笑说“圆场”，很过分吗？请问哪里
: 不负责任了。好吧，如果比如你这类非当事人觉得很过分，那我之前也道歉过了，有则
: 改之无则加勉，OK的。
: 可是你呢？作为业外人士，玩笑当然没问题，冷嘲热讽都合情合理，但是不是当事人却
: 刻意的以当事人的口吻，揭示所谓内幕消息，挑起无关的矛盾，这就不是最后一句开玩

j*x2012-11-24 08:11

48 楼

如果是当事人，你敏感我不介意，难免的
局外人业外人士，你敏感就让我有点莫名其妙了
我敏感的恰恰就是你这种双面人的身份，你能正面回答一下吗？

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

: 呵呵，我是敏感了，你不觉得你也是吗？

d*j2012-11-24 08:11

49 楼

本人生物WSN一个，没事儿网上发发牢骚，你就别瞎想了。
我本人无论在具体工作上还是科研项目上与受体的发现与炒作、NIBS、RY没有任何利益
关系。
如果给大家造成这个印象，实在抱歉。

【在 j****x 的大作中提到】

: 如果是当事人，你敏感我不介意，难免的
: 局外人业外人士，你敏感就让我有点莫名其妙了
: 我敏感的恰恰就是你这种双面人的身份，你能正面回答一下吗？

D*a2012-11-24 08:11

50 楼

俺也不是搞病毒的，不懂那么多。但是如果说不是受体，那么为啥把它转到不能感染的
细胞上就能感染了？难道只要有了宿主因子，没有受体也能感染？
但是后面说到饶毅什么的，跟研究也没啥关系吧。国内领导喜欢造势，大家又不是第一
天才知道。
倒是eLife通过这个事在华人里面和病毒里面知名度一下子就上去了，呵呵。这两年这
篇文章引用应该不低，我是真心希望它能跟CNS抗衡，或者至少能到20多分，动摇一下
腐朽的审稿制度。

w*e2012-11-24 08:11

51 楼

要允许别人说话，百家争鸣，一言堂不好

【在 j****x 的大作中提到】

: 我觉得你还是做好你自己的事情吧，如果你不是当事人之一，最好不要在这里瞎搅混水
: ，妄谈science之外的事情，既不能代表当事人的真实想法，更会带来外界的猜疑和误
: 会。
:
: 系(

j*x2012-11-24 08:11

52 楼

质疑者会认为，受体在不能感染的细胞上本身就存在，而缺的就是这个“宿主因子”。
如果无视其他证据的话，这种解释也不能说不成立。
至于elife，华人中的知名度是上去了，但是看着本版这架势，毁过于誉吧，未必是啥
好事

【在 D*a 的大作中提到】

: 俺也不是搞病毒的，不懂那么多。但是如果说不是受体，那么为啥把它转到不能感染的
: 细胞上就能感染了？难道只要有了宿主因子，没有受体也能感染？
: 但是后面说到饶毅什么的，跟研究也没啥关系吧。国内领导喜欢造势，大家又不是第一
: 天才知道。
: 倒是eLife通过这个事在华人里面和病毒里面知名度一下子就上去了，呵呵。这两年这
: 篇文章引用应该不低，我是真心希望它能跟CNS抗衡，或者至少能到20多分，动摇一下
: 腐朽的审稿制度。

j*x2012-11-24 08:11

53 楼

发表自己的个人观点难道还有人拦着不成？

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

: 要允许别人说话，百家争鸣，一言堂不好

w*e2012-11-24 08:11

54 楼

“最好不要在这里瞎搅混水”意思是？

【在 j****x 的大作中提到】

: 发表自己的个人观点难道还有人拦着不成？

j*x2012-11-24 08:11

55 楼

先看清前后文吧
这位朋友并不是当事人，但是好几次以当事人的口气（至少我一开始就被误导了）来描
述李博士方面的一些具体的思想活动细节以及NIBS内部的一些未见证实的意见冲突和矛
盾，我针对的是这一情况
如果这位朋友是当事人之一或者内部人士，那么说这些倒也无可厚非，但是他本人之前
已否认了和整件事有任何瓜葛，那么这种情况下，我认为他说话的立场和方式有问题，
容易产生误导，不该刻意的以当事人的口吻发表自己主观的评论，“最好不要瞎搅混水
”，这就是搞一言堂了吗？

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

: “最好不要在这里瞎搅混水”意思是？

S*s2012-11-24 08:11

56 楼

正解。

【在 j****x 的大作中提到】

: 先看清前后文吧
: 这位朋友并不是当事人，但是好几次以当事人的口气（至少我一开始就被误导了）来描
: 述李博士方面的一些具体的思想活动细节以及NIBS内部的一些未见证实的意见冲突和矛
: 盾，我针对的是这一情况
: 如果这位朋友是当事人之一或者内部人士，那么说这些倒也无可厚非，但是他本人之前
: 已否认了和整件事有任何瓜葛，那么这种情况下，我认为他说话的立场和方式有问题，
: 容易产生误导，不该刻意的以当事人的口吻发表自己主观的评论，“最好不要瞎搅混水
: ”，这就是搞一言堂了吗？

d*j2012-11-24 08:11

57 楼

补充你提到的两点
描述李博士方面的一些具体的思想活动细节---我刚才已经解释了,因为你的走穴/圆场
的描述,我才说的”我认为对目前的炒作,李被逼无奈,身不由己,不想再烦了”,你既然
把你说的当成玩笑,请把我说的也当成是玩笑.
NIBS内部的一些未见证实的意见冲突和矛盾---这个你不要混淆了,我没有说李与NIBS内
部有什么意见冲突.我在别的贴子里提到的NIBS其他PI离开的原因,虽然没有提到具体人
,我对我说的话负责.而且请不要混淆了我类比到其他学校的内部矛盾.

【在 j****x 的大作中提到】

: 先看清前后文吧
: 这位朋友并不是当事人，但是好几次以当事人的口气（至少我一开始就被误导了）来描
: 述李博士方面的一些具体的思想活动细节以及NIBS内部的一些未见证实的意见冲突和矛
: 盾，我针对的是这一情况
: 如果这位朋友是当事人之一或者内部人士，那么说这些倒也无可厚非，但是他本人之前
: 已否认了和整件事有任何瓜葛，那么这种情况下，我认为他说话的立场和方式有问题，
: 容易产生误导，不该刻意的以当事人的口吻发表自己主观的评论，“最好不要瞎搅混水
: ”，这就是搞一言堂了吗？

j*x2012-11-24 08:11

58 楼

我是用我自己的身份开玩笑，你是在用李博士或者相关当事人的身份开玩笑，请不要混
淆了。这也是我后面所有态度和立场的根源。
你没有说李和NIBS内部有什么意见冲突？是谁说是被逼获奖？是谁说被拒后要投JV却被
强行要求投到elife？被逼无奈，身不由己，这也不是意见冲突？
我们都请自重吧，言尽于此了

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

: 补充你提到的两点
: 描述李博士方面的一些具体的思想活动细节---我刚才已经解释了,因为你的走穴/圆场
: 的描述,我才说的”我认为对目前的炒作,李被逼无奈,身不由己,不想再烦了”,你既然
: 把你说的当成玩笑,请把我说的也当成是玩笑.
: NIBS内部的一些未见证实的意见冲突和矛盾---这个你不要混淆了,我没有说李与NIBS内
: 部有什么意见冲突.我在别的贴子里提到的NIBS其他PI离开的原因,虽然没有提到具体人
: ,我对我说的话负责.而且请不要混淆了我类比到其他学校的内部矛盾.

d*j2012-11-24 08:11

59 楼

你说这个获奖这件事儿啊，我没相信我没说错的。因为我不相信李博士自己会在结果还
没发表之前，自己提名自己去评奖。
后面关于投杂志，我觉得我是在当时语境下的推论。我说了，大家因为我对李博士如果
有什么误解，我很抱歉。但是我保留我对相关单位领导的评价。
既然你前后这么样推断我，我也礼尚往来一下。其实同学你是有意无意的认为，NIBS及
其他新派单位代表着完美的体制，代表着光荣正确伟大。所以你才敏感。很抱歉，我的
发言/调侃给人泼脏水了

【在 j****x 的大作中提到】

: 我是用我自己的身份开玩笑，你是在用李博士或者相关当事人的身份开玩笑，请不要混
: 淆了。这也是我后面所有态度和立场的根源。
: 你没有说李和NIBS内部有什么意见冲突？是谁说是被逼获奖？是谁说被拒后要投JV却被
: 强行要求投到elife？被逼无奈，身不由己，这也不是意见冲突？
: 我们都请自重吧，言尽于此了

j*x2012-11-24 08:11

60 楼

简直是笑话，我所有的帖子，从来没提过NIBS体制一根毛（除了回你的2个帖子我连
NIBS都没扯过半句），NIBS啥模式啥机制关我p事，我只讨论李博士本身的结果及意义
，而且我从头到尾一直在强调，let science talks，别扯别的啥狗屁。
你自己说过的话不承认了，对于种种无端的意见冲突的表述，你又语焉不详了？然后开
始给我泼脏水了？你敢不敢承认嘛，是男人吗？

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

: 你说这个获奖这件事儿啊，我没相信我没说错的。因为我不相信李博士自己会在结果还
: 没发表之前，自己提名自己去评奖。
: 后面关于投杂志，我觉得我是在当时语境下的推论。我说了，大家因为我对李博士如果
: 有什么误解，我很抱歉。但是我保留我对相关单位领导的评价。
: 既然你前后这么样推断我，我也礼尚往来一下。其实同学你是有意无意的认为，NIBS及
: 其他新派单位代表着完美的体制，代表着光荣正确伟大。所以你才敏感。很抱歉，我的
: 发言/调侃给人泼脏水了

d*j2012-11-24 08:11

61 楼

老天，同学，你生气了？至于吗？
好了好了，我给你泼脏水了，我道歉。我给王晓东NIBS道歉。

【在 j****x 的大作中提到】

: 简直是笑话，我所有的帖子，从来没提过NIBS体制一根毛（除了回你的2个帖子我连
: NIBS都没扯过半句），NIBS啥模式啥机制关我p事，我只讨论李博士本身的结果及意义
: ，而且我从头到尾一直在强调，let science talks，别扯别的啥狗屁。
: 你自己说过的话不承认了，对于种种无端的意见冲突的表述，你又语焉不详了？然后开
: 始给我泼脏水了？你敢不敢承认嘛，是男人吗？

j*x2012-11-24 08:11

62 楼

省省吧，谁值得为这事生气。
说自己的话做自己的事，别骂个娘还要借别人的话头，让人看扁了

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

: 老天，同学，你生气了？至于吗？
: 好了好了，我给你泼脏水了，我道歉。我给王晓东NIBS道歉。

d*j2012-11-24 08:11

63 楼

呵呵，没生气就好。
看扁了就看扁吧。当然了，你对我自己专门发贴骂RY等人的主题不感兴趣，你是好学生。
这事儿，从我这里，主要是我无聊了，抱歉。

【在 j****x 的大作中提到】

: 省省吧，谁值得为这事生气。
: 说自己的话做自己的事，别骂个娘还要借别人的话头，让人看扁了

m*c2012-11-24 08:11

64 楼

thanks juzbox, for your detailed posts on the scientific parts of the paper.
I'm a complete outsider but learned much info from your post.