i**********b
发帖数: 77 | 1 how to find out the median in a stream.
大家谁有办法？ |
y****w
发帖数: 3747 | 2 空间复杂度要求？
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
|
x******3
发帖数: 245 | 3 用一个dynamic set，比如RBT来保存stream里的值， 然后在RBT里查找median
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
|
i**********b
发帖数: 77 | 4 所谓 stream, 就是说real time data， 不间断。
是个有限空间解决无限数据流的问题。
全都存肯定不行。
空间复杂度的问题不用考虑。 big O 在这个问题里不管用 |
z*******e
发帖数: 122 | 5 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 |
x******3
发帖数: 245 | 6 可以设定RBT的上限size， 存不下的时候， 除掉最左边和最右边的值， 这样保持中值
不变
【在 i**********b 的大作中提到】
: 所谓 stream, 就是说real time data， 不间断。
: 是个有限空间解决无限数据流的问题。
: 全都存肯定不行。
: 空间复杂度的问题不用考虑。 big O 在这个问题里不管用
|
w****l
发帖数: 88 | 7 问一下： 什么是RBT啊？具体过程怎么样呢？
另外，如果用两个堆，这两个堆怎么初始化呢？ |
x******3
发帖数: 245 | 8 Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
点中保存子树大小，来方便查找中
值
你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
小是100， 说明树满了， 删除最左
边和最右边的节点来保持中值不变， 再插入新数据
【在 w****l 的大作中提到】
: 问一下： 什么是RBT啊？具体过程怎么样呢？
: 另外，如果用两个堆，这两个堆怎么初始化呢？
|
b****r
发帖数: 1272 | 9 RBT的SIZE怎么决定呢 1000，100，甚至10？
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
|
w****l
发帖数: 88 | 10 你的意思是： RBT的根节点总是记录了当前子树的中数对么？
【在 x******3 的大作中提到】
: Red Black Tree, 就是一种balanced search tree, binary search tree 加强版
: stream data是不断产生的， 所以每当一个新数据产生了，就插入RBT， 还要在每个节
: 点中保存子树大小，来方便查找中
: 值
: 你可以设定RBT最多保存100个节点， 然后在新插入节点前， 检查如果根节点的子树大
: 小是100， 说明树满了， 删除最左
: 边和最右边的节点来保持中值不变， 再插入新数据
|
|
|
b******v
发帖数: 1493 | 11 假设这种情形：
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
发帖数: 292 | 12 我衷心的向 zixujoyce 和 xbeast23 大侠致敬。感受到一些灵感在里面。
我以后就在这个版混了。。。。。 |
x******3
发帖数: 245 | 13 不好意思， 没考虑全面，:)
这样的话， 好像不能乱删除节点， 不然后面的中值query可能出错
【在 b******v 的大作中提到】
: 假设这种情形：
: stream是1,2,3,4, ...，也就是所有自然数按次序进入stream
: 如果你的RBT最多保存100个节点，则在插入101时，你会删除1和100
: 可是当stream到199时，这时的median应该是100，可是100已经不在你的RBT里面了
|
x******3
发帖数: 245 | 14 保存子树中的节点个数， 查找中值的就可以判断中值应该在那边的子树里
比如你的根节点里子树大小是9，中值就是rank是5的值，
如果左边子树大小是3，右边是5，你应该在右边子树中找rank是1（5-3-1）的值
这样的话查找的时间就是树高， RBT的话就是lgn
【在 w****l 的大作中提到】
: 你的意思是： RBT的根节点总是记录了当前子树的中数对么？
|
b******v
发帖数: 1493 | 15 我感觉这道题好像无解
因为如果没有保存所有值的话，必定有某一个x被扔掉了
这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
这样就无法找到median值
【在 x******3 的大作中提到】
: 不好意思， 没考虑全面，:)
: 这样的话， 好像不能乱删除节点， 不然后面的中值query可能出错
|
x******3
发帖数: 245 | 16 我觉得这个interviewer也没想这么深，：）
他大概也就想让你说， stream是dynamic， 所以要用dynamic set来存数据， 然后想
让你说怎么在dynamic set里做
order statistics
【在 b******v 的大作中提到】
: 我感觉这道题好像无解
: 因为如果没有保存所有值的话，必定有某一个x被扔掉了
: 这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
: 这样就无法找到median值
|
r****o
发帖数: 1950 | 17 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
|
f**r
发帖数: 865 | 18 象这种问题只能做sampling吧，感觉问题的关键是找到一个unbiased sample |
g*****u
发帖数: 298 | 19 同意。
上面说用两个heap的，必然要保存所有值（case 2），否则会导致结果不正确。
【在 b******v 的大作中提到】
: 我感觉这道题好像无解
: 因为如果没有保存所有值的话，必定有某一个x被扔掉了
: 这样我们可以轻易选择stream后面的值，使得到某一点时，x为median
: 这样就无法找到median值
|
B***i
发帖数: 724 | 20 想起来了
我老在四年前被一个老印 在一个indian buffeit店里lunch interview的时候就是这个
问题 |
|
|
f****7
发帖数: 6 | 21 是取决于sample的方式,看过解答,可惜忘记了. |
r******g
发帖数: 58 | 22
“有限空间解决无限问题”，觉得不行，要是不完全保留数据，肯定到时候有median丢
失。
【在 i**********b 的大作中提到】
: 所谓 stream, 就是说real time data， 不间断。
: 是个有限空间解决无限数据流的问题。
: 全都存肯定不行。
: 空间复杂度的问题不用考虑。 big O 在这个问题里不管用
|
t**n
发帖数: 272 | 23 如果条件就是这样的话无解
如果input stream的值有值域范围,有办法
【在 i**********b 的大作中提到】
: how to find out the median in a stream.
: 大家谁有办法？
|
