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,只放一百个数就够了
可能3个就行
【在 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,只放一百个数就够了 : 可能3个就行
|
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起来很麻烦的。 : : 道数 : 道数
|