L*i
2 楼
我的答案是否定的。首先，天下乌鸦一般黑，周董玩过那么多女人，怎么可能被一个93
年的小模特给拴一辈子。而且即便与昆凌结了婚生了小周周，周围想投怀送抱的女人岂
是你我凡人能数清楚的，从这里看，昆凌天王嫂的地位其实并没有那么稳固，用风雨飘
摇这个词来形容我觉得是不过分的。
这年头，就拿普通人来说，两个人就算是结了婚生了孩子，其实也并不能说明什么，孩
子并不是婚姻长久的砝码。如果认为用孩子可以拴住男人，那众所周知的梁洛施呢，为
某凯生了三个大胖小子之后，还不是一样被扫地出门，被甩了。所以生了孩子并不表示
自己就会是男人的最后一个女人，要不然怎么会有“出轨”、“小三”、“情人”这些
词呢，哈哈。
昆凌绝不会是周董最后一个女人，玩音乐的人思想都很开放，周董找一个比自己小十几
岁的小姑娘，无非就是想要多生宝宝罢了。试想，如果周董找的是跟自己同龄或只小一
点的，那生孩子的时候不就成了高龄产妇了吗，如何满足周董想要生很多宝宝的愿望呢
。从这个角度来看，如果昆凌只是一个生孩子工具的话，那她绝不是周董最后一个女人。
年的小模特给拴一辈子。而且即便与昆凌结了婚生了小周周，周围想投怀送抱的女人岂
是你我凡人能数清楚的，从这里看，昆凌天王嫂的地位其实并没有那么稳固，用风雨飘
摇这个词来形容我觉得是不过分的。
这年头，就拿普通人来说，两个人就算是结了婚生了孩子，其实也并不能说明什么，孩
子并不是婚姻长久的砝码。如果认为用孩子可以拴住男人，那众所周知的梁洛施呢，为
某凯生了三个大胖小子之后，还不是一样被扫地出门，被甩了。所以生了孩子并不表示
自己就会是男人的最后一个女人，要不然怎么会有“出轨”、“小三”、“情人”这些
词呢，哈哈。
昆凌绝不会是周董最后一个女人，玩音乐的人思想都很开放，周董找一个比自己小十几
岁的小姑娘，无非就是想要多生宝宝罢了。试想，如果周董找的是跟自己同龄或只小一
点的，那生孩子的时候不就成了高龄产妇了吗，如何满足周董想要生很多宝宝的愿望呢
。从这个角度来看，如果昆凌只是一个生孩子工具的话，那她绝不是周董最后一个女人。
z*9
3 楼
住在大农村休斯顿想在后院养鸡，不知是否可行?希望指点谢谢!
l*n
4 楼
BBS上G家的人也不少啊。
主要是Apple的问题来回来去都已经被大家讲的很透彻了。
主要是Apple的问题来回来去都已经被大家讲的很透彻了。
y*w
5 楼
空间复杂度要求？
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
m*6
6 楼
你要去问一下你们CITY有什么规定。
w*c
7 楼
去pda版看goodbug的评论就好，lol
【在 l**n 的大作中提到】
: BBS上G家的人也不少啊。
: 主要是Apple的问题来回来去都已经被大家讲的很透彻了。
【在 l**n 的大作中提到】
: BBS上G家的人也不少啊。
: 主要是Apple的问题来回来去都已经被大家讲的很透彻了。
x*3
8 楼
用一个dynamic set，比如RBT来保存stream里的值， 然后在RBT里查找median
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
y*8
9 楼
Ｒｅ. 还要问一下ｈｏａ有什么规定。
【在 m**6 的大作中提到】
: 你要去问一下你们CITY有什么规定。
【在 m**6 的大作中提到】
: 你要去问一下你们CITY有什么规定。
a*a
10 楼
那你还不如去看老大爷贴的gay 黄图呢
【在 w******c 的大作中提到】
: 去pda版看goodbug的评论就好，lol
【在 w******c 的大作中提到】
: 去pda版看goodbug的评论就好，lol
i*b
11 楼
所谓 stream, 就是说real time data， 不间断。
是个有限空间解决无限数据流的问题。
全都存肯定不行。
空间复杂度的问题不用考虑。 big O 在这个问题里不管用
是个有限空间解决无限数据流的问题。
全都存肯定不行。
空间复杂度的问题不用考虑。 big O 在这个问题里不管用
p*9
12 楼
lol
【在 a****a 的大作中提到】
: 那你还不如去看老大爷贴的gay 黄图呢
【在 a****a 的大作中提到】
: 那你还不如去看老大爷贴的gay 黄图呢
z*e
13 楼
Use two heaps. The left heap is a max heap, the right heap is a min heap.
Between the two heap, there is a number indicating the current median number
. When a new number comes in, we take the following operations (notice that
the two heap must have the same number of values, actually the left heap
stores all the numbers smaller than the median, and the right heap contains
the numbers larger than the median), we should also have a flag variable to
indicate whether the current median is in the s
Between the two heap, there is a number indicating the current median number
. When a new number comes in, we take the following operations (notice that
the two heap must have the same number of values, actually the left heap
stores all the numbers smaller than the median, and the right heap contains
the numbers larger than the median), we should also have a flag variable to
indicate whether the current median is in the s
x*3
14 楼
可以设定RBT的上限size， 存不下的时候， 除掉最左边和最右边的值， 这样保持中值
不变
【在 i**********b 的大作中提到】
: 所谓 stream, 就是说real time data， 不间断。
: 是个有限空间解决无限数据流的问题。
: 全都存肯定不行。
: 空间复杂度的问题不用考虑。 big O 在这个问题里不管用
不变
【在 i**********b 的大作中提到】
: 所谓 stream, 就是说real time data， 不间断。
: 是个有限空间解决无限数据流的问题。
: 全都存肯定不行。
: 空间复杂度的问题不用考虑。 big O 在这个问题里不管用
w*l
15 楼
问一下： 什么是RBT啊？具体过程怎么样呢？
另外，如果用两个堆，这两个堆怎么初始化呢？
另外，如果用两个堆，这两个堆怎么初始化呢？
x*3
16 楼
Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
点中保存子树大小，来方便查找中
值
你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
小是100， 说明树满了， 删除最左
边和最右边的节点来保持中值不变， 再插入新数据
【在 w****l 的大作中提到】
: 问一下： 什么是RBT啊？具体过程怎么样呢？
: 另外，如果用两个堆，这两个堆怎么初始化呢？
stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
点中保存子树大小，来方便查找中
值
你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
小是100， 说明树满了， 删除最左
边和最右边的节点来保持中值不变， 再插入新数据
【在 w****l 的大作中提到】
: 问一下： 什么是RBT啊？具体过程怎么样呢？
: 另外，如果用两个堆，这两个堆怎么初始化呢？
b*r
17 楼
RBT的SIZE怎么决定呢 1000，100，甚至10？
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
w*l
18 楼
你的意思是： RBT的根节点总是记录了当前子树的中数对么？
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
b*v
19 楼
假设这种情形：
stream是1,2,3,4, ...，也就是所有自然数按次序进入stream
如果你的RBT最多保存100个节点，则在插入101时，你会删除1和100
可是当stream到199时，这时的median应该是100，可是100已经不在你的RBT里面了
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
stream是1,2,3,4, ...，也就是所有自然数按次序进入stream
如果你的RBT最多保存100个节点，则在插入101时，你会删除1和100
可是当stream到199时，这时的median应该是100，可是100已经不在你的RBT里面了
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
r*1
20 楼
我衷心的向 zixujoyce 和 xbeast23 大侠致敬。感受到一些灵感在里面。
我以后就在这个版混了。。。。。
我以后就在这个版混了。。。。。
x*3
21 楼
不好意思， 没考虑全面，:)
这样的话， 好像不能乱删除节点， 不然后面的中值query可能出错
【在 b******v 的大作中提到】
: 假设这种情形：
: stream是1,2,3,4, ...，也就是所有自然数按次序进入stream
: 如果你的RBT最多保存100个节点，则在插入101时，你会删除1和100
: 可是当stream到199时，这时的median应该是100，可是100已经不在你的RBT里面了
这样的话， 好像不能乱删除节点， 不然后面的中值query可能出错
【在 b******v 的大作中提到】
: 假设这种情形：
: stream是1,2,3,4, ...，也就是所有自然数按次序进入stream
: 如果你的RBT最多保存100个节点，则在插入101时，你会删除1和100
: 可是当stream到199时，这时的median应该是100，可是100已经不在你的RBT里面了
x*3
22 楼
保存子树中的节点个数， 查找中值的就可以判断中值应该在那边的子树里
比如你的根节点里子树大小是9，中值就是rank是5的值，
如果左边子树大小是3，右边是5，你应该在右边子树中找rank是1（5-3-1）的值
这样的话查找的时间就是树高， RBT的话就是lgn
【在 w****l 的大作中提到】
: 你的意思是： RBT的根节点总是记录了当前子树的中数对么？
比如你的根节点里子树大小是9，中值就是rank是5的值，
如果左边子树大小是3，右边是5，你应该在右边子树中找rank是1（5-3-1）的值
这样的话查找的时间就是树高， RBT的话就是lgn
【在 w****l 的大作中提到】
: 你的意思是： RBT的根节点总是记录了当前子树的中数对么？
b*v
23 楼
我感觉这道题好像无解
因为如果没有保存所有值的话，必定有某一个x被扔掉了
这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
这样就无法找到median值
【在 x******3 的大作中提到】
: 不好意思， 没考虑全面，:)
: 这样的话， 好像不能乱删除节点， 不然后面的中值query可能出错
因为如果没有保存所有值的话，必定有某一个x被扔掉了
这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
这样就无法找到median值
【在 x******3 的大作中提到】
: 不好意思， 没考虑全面，:)
: 这样的话， 好像不能乱删除节点， 不然后面的中值query可能出错
x*3
24 楼
我觉得这个interviewer也没想这么深，：）
他大概也就想让你说， stream是dynamic， 所以要用dynamic set来存数据， 然后想
让你说怎么在dynamic set里做
order statistics
【在 b******v 的大作中提到】
: 我感觉这道题好像无解
: 因为如果没有保存所有值的话，必定有某一个x被扔掉了
: 这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
: 这样就无法找到median值
他大概也就想让你说， stream是dynamic， 所以要用dynamic set来存数据， 然后想
让你说怎么在dynamic set里做
order statistics
【在 b******v 的大作中提到】
: 我感觉这道题好像无解
: 因为如果没有保存所有值的话，必定有某一个x被扔掉了
: 这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
: 这样就无法找到median值
r*o
25 楼
what is the size of the two heaps?
number
that
contains
to
in
【在 z*******e 的大作中提到】
: Use two heaps. The left heap is a max heap, the right heap is a min heap.
: Between the two heap, there is a number indicating the current median number
: . When a new number comes in, we take the following operations (notice that
: the two heap must have the same number of values, actually the left heap
: stores all the numbers smaller than the median, and the right heap contains
: the numbers larger than the median), we should also have a flag variable to
: indicate whether the current median is in the s
number
that
contains
to
in
【在 z*******e 的大作中提到】
: Use two heaps. The left heap is a max heap, the right heap is a min heap.
: Between the two heap, there is a number indicating the current median number
: . When a new number comes in, we take the following operations (notice that
: the two heap must have the same number of values, actually the left heap
: stores all the numbers smaller than the median, and the right heap contains
: the numbers larger than the median), we should also have a flag variable to
: indicate whether the current median is in the s
f*r
26 楼
象这种问题只能做sampling吧，感觉问题的关键是找到一个unbiased sample
g*u
27 楼
同意。
上面说用两个heap的，必然要保存所有值（case 2），否则会导致结果不正确。
【在 b******v 的大作中提到】
: 我感觉这道题好像无解
: 因为如果没有保存所有值的话，必定有某一个x被扔掉了
: 这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
: 这样就无法找到median值
上面说用两个heap的，必然要保存所有值（case 2），否则会导致结果不正确。
【在 b******v 的大作中提到】
: 我感觉这道题好像无解
: 因为如果没有保存所有值的话，必定有某一个x被扔掉了
: 这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
: 这样就无法找到median值
B*i
28 楼
想起来了
我老在四年前被一个老印 在一个indian buffeit店里lunch interview的时候就是这个
问题
我老在四年前被一个老印 在一个indian buffeit店里lunch interview的时候就是这个
问题
f*7
29 楼
是取决于sample的方式,看过解答,可惜忘记了.
r*g
30 楼
“有限空间解决无限问题”，觉得不行，要是不完全保留数据，肯定到时候有median丢
失。
【在 i**********b 的大作中提到】
: 所谓 stream, 就是说real time data， 不间断。
: 是个有限空间解决无限数据流的问题。
: 全都存肯定不行。
: 空间复杂度的问题不用考虑。 big O 在这个问题里不管用
t*n
31 楼
如果条件就是这样的话无解
如果input stream的值有值域范围,有办法
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
如果input stream的值有值域范围,有办法
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
相关阅读
一个3g模块要加100多？bing的iphone app还真是不错关于*thehutt ID的处理情况。Apple iPad: women's best friend (转载)iPad的一个亮点iTouch vs. Zune苹果的东西做的真不错还是教主厉害大家说说Mac Book到底好在哪里？租这么个地半天得花多少钱？菜鸟问：看avi必须要安Quicktime pro吗？请问国内网银只用IE的问题大家怎么解决的？比较Google, MS, Apple, Yahoo的领域还有一个原因为什么苹果要把有些功能省略掉iPad refurbished已经有了iphone，还要给iPad再买一个data plan?9.7寸屏幕咋边框那么厚实。。。想搞两个iphone回去送人，怎么操作？anyone here has a kindle?