m******a
发帖数: 84 | 1 there is a data flow, find the median of the data in a given time interval.
有什么好的算法么？比如数据不停的流进来，然后给N查询区间[time1, tim2]，求区间
中位数 |
s*****n
发帖数: 134 | 2 造一个最大堆，一个最小堆，然后把数据流里进来的数和两个堆的根节点做比较 |
m******a
发帖数: 84 | 3 这个是求从开始到目前的中位数，但是这个问题是求从开始到目前的任一区间的中位数
，这个要怎么求 呢？ |
h**********c
发帖数: 4120 | 4 这个题觉得，经过缜密的休息,refresh
觉得
觉得
binary search tree 比较好
如果你比较坑z-turn,自己搞一个linked binary search tree map
.
【在 m******a 的大作中提到】
: there is a data flow, find the median of the data in a given time interval.
: 有什么好的算法么？比如数据不停的流进来，然后给N查询区间[time1, tim2]，求区间
: 中位数
|
w****a
发帖数: 710 | |
n*******s
发帖数: 17267 | 6 这种背答案的题totally defeats the interview purpose, 面试想看的是你怎么思考
和解决问题的， 但现在是个人就可以把答案先看了， 然后开始BS， LOL。 |
m******a
发帖数: 84 | 7 能详细一点么？
【在 h**********c 的大作中提到】
: 这个题觉得，经过缜密的休息,refresh
: 觉得
: 觉得
: binary search tree 比较好
: 如果你比较坑z-turn,自己搞一个linked binary search tree map
:
: .
|
h**********c
发帖数: 4120 | 8 就是把tree map的node加上prev，next的reference
insert 的时候，zturn, z-turn
good luck
【在 m******a 的大作中提到】
: 能详细一点么？
|
m******a
发帖数: 84 | 9 tree map 就是java中的tree map吧，zturn , z-turn是什么意思呢？
【在 h**********c 的大作中提到】
: 就是把tree map的node加上prev，next的reference
: insert 的时候，zturn, z-turn
: good luck
|
h**********c
发帖数: 4120 | 10 估计可能要down tree,up tree,
你愿意折腾的话，还可以balance
你记住中数的reference的位置
前面插，移到next
后面插，移到prev
bst
有点忘了
regards |
|
|
g********k
发帖数: 838 | 11 当N很大时，找median其实很困难的，需要排序
不过如果distribution比较好（symmetric），可以用mean来代替。或者存一个table记
录区间内出现的个数，这个可以快速找到近似中位数（好处还是可以自己控制
precision）
总之big data找median是非常困难的问题。
.
【在 m******a 的大作中提到】
: there is a data flow, find the median of the data in a given time interval.
: 有什么好的算法么？比如数据不停的流进来，然后给N查询区间[time1, tim2]，求区间
: 中位数
|
h**********c
发帖数: 4120 | 12 You are right, you are the best google search scientist. sincerely.
其实那个tree map，只放一百个数就够了
可能３个就行
【在 g********k 的大作中提到】
: 当N很大时，找median其实很困难的，需要排序
: 不过如果distribution比较好（symmetric），可以用mean来代替。或者存一个table记
: 录区间内出现的个数，这个可以快速找到近似中位数（好处还是可以自己控制
: precision）
: 总之big data找median是非常困难的问题。
:
: .
|
g********k
发帖数: 838 | 13 我不是google search scientist。。。
是我面试也遇到过这个问题（open ended，所以没有正确答案），不过我不懂binary
tree怎么解，你能具体讲讲嘛，我不是CS科班的。
【在 h**********c 的大作中提到】
: You are right, you are the best google search scientist. sincerely.
: 其实那个tree map，只放一百个数就够了
: 可能３个就行
|
h**********c
发帖数: 4120 | 14 想法不太成熟
不是记录一个中间数，而是纪录一个中间段
来的大数，小数都不进中间段
但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
凑合
这样不用对整个interval 排序
如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
【在 g********k 的大作中提到】
: 我不是google search scientist。。。
: 是我面试也遇到过这个问题（open ended，所以没有正确答案），不过我不懂binary
: tree怎么解，你能具体讲讲嘛，我不是CS科班的。
|
h**********c
发帖数: 4120 | 15 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
数据还是很bias的话，还是问题
【在 h**********c 的大作中提到】
: 想法不太成熟
: 不是记录一个中间数，而是纪录一个中间段
: 来的大数，小数都不进中间段
: 但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
: 凑合
: 这样不用对整个interval 排序
: 如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
|
h**********c
发帖数: 4120 | 16 数据很bias 的话，可以preprocess 中间段个数，
或preprocess 若干个数，以免中间段完全左倾活右倾或
差不多了，
道数
道数
【在 h**********c 的大作中提到】
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 数据还是很bias的话，还是问题
|
g********k
发帖数: 838 | 17 这个是可行的，但是如何确定中间段呢，如果来的data比较大，需要中间段移动很大的
话，就不好了。所以worst case还是需要排序的。
【在 h**********c 的大作中提到】
: 想法不太成熟
: 不是记录一个中间数，而是纪录一个中间段
: 来的大数，小数都不进中间段
: 但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
: 凑合
: 这样不用对整个interval 排序
: 如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
|
g********k
发帖数: 838 | 18 对，我说的也是这个，如果遇到bad data，这个方法code起来很麻烦的。
道数
道数
【在 h**********c 的大作中提到】
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 数据还是很bias的话，还是问题
|
h**********c
发帖数: 4120 | 19 如果bad data，cache 若干段
mix bias段with non-bias 短
preprocess
【在 g********k 的大作中提到】
: 对，我说的也是这个，如果遇到bad data，这个方法code起来很麻烦的。
:
: 道数
: 道数
|
