华盛顿地区有可靠的车行吗？ (转载)# Automobile - 车轮上的传奇
m*a
1 楼
there is a data flow, find the median of the data in a given time interval.
有什么好的算法么？比如数据不停的流进来，然后给N查询区间[time1, tim2]，求区间
中位数
有什么好的算法么？比如数据不停的流进来，然后给N查询区间[time1, tim2]，求区间
中位数
G*9
2 楼
【 以下文字转载自 WashingtonDC 讨论区 】
发信人: Great2009 (Wonderful!), 信区: WashingtonDC
标 题: 华盛顿地区有可靠的车行吗？
发信站: BBS 未名空间站 (Tue Sep 13 17:43:40 2011, 美东)
我的老车看来需要好好修一下了。但是天下车行好像绝大多数都很黑。
大家有什么推荐的吗？
发信人: Great2009 (Wonderful!), 信区: WashingtonDC
标 题: 华盛顿地区有可靠的车行吗？
发信站: BBS 未名空间站 (Tue Sep 13 17:43:40 2011, 美东)
我的老车看来需要好好修一下了。但是天下车行好像绝大多数都很黑。
大家有什么推荐的吗？
s*n
3 楼
造一个最大堆，一个最小堆，然后把数据流里进来的数和两个堆的根节点做比较
c*2
4 楼
是DC地区，华盛顿一般指西雅图那边。
DC不知道,大华府区好的修车铺还真不少，我们这边Rockville,Gaithersburg就有好几
个很实在的华人修车铺。
DC不知道,大华府区好的修车铺还真不少，我们这边Rockville,Gaithersburg就有好几
个很实在的华人修车铺。
m*a
5 楼
这个是求从开始到目前的中位数，但是这个问题是求从开始到目前的任一区间的中位数
，这个要怎么求 呢？
，这个要怎么求 呢？
G*9
6 楼
可否提供具体信息，谢谢！
【在 c******2 的大作中提到】
: 是DC地区，华盛顿一般指西雅图那边。
: DC不知道,大华府区好的修车铺还真不少，我们这边Rockville,Gaithersburg就有好几
: 个很实在的华人修车铺。
【在 c******2 的大作中提到】
: 是DC地区，华盛顿一般指西雅图那边。
: DC不知道,大华府区好的修车铺还真不少，我们这边Rockville,Gaithersburg就有好几
: 个很实在的华人修车铺。
h*c
7 楼
这个题觉得，经过缜密的休息,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]，求区间
: 中位数
觉得
觉得
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
8 楼
这个好像是最近高频题
n*s
9 楼
这种背答案的题totally defeats the interview purpose, 面试想看的是你怎么思考
和解决问题的， 但现在是个人就可以把答案先看了， 然后开始BS， LOL。
和解决问题的， 但现在是个人就可以把答案先看了， 然后开始BS， LOL。
m*a
10 楼
能详细一点么？
【在 h**********c 的大作中提到】
: 这个题觉得，经过缜密的休息,refresh
: 觉得
: 觉得
: binary search tree 比较好
: 如果你比较坑z-turn,自己搞一个linked binary search tree map
:
: .
【在 h**********c 的大作中提到】
: 这个题觉得，经过缜密的休息,refresh
: 觉得
: 觉得
: binary search tree 比较好
: 如果你比较坑z-turn,自己搞一个linked binary search tree map
:
: .
h*c
11 楼
就是把tree map的node加上prev，next的reference
insert 的时候，zturn, z-turn
good luck
【在 m******a 的大作中提到】
: 能详细一点么？
insert 的时候，zturn, z-turn
good luck
【在 m******a 的大作中提到】
: 能详细一点么？
m*a
12 楼
tree map 就是java中的tree map吧，zturn , z-turn是什么意思呢？
【在 h**********c 的大作中提到】
: 就是把tree map的node加上prev，next的reference
: insert 的时候，zturn, z-turn
: good luck
【在 h**********c 的大作中提到】
: 就是把tree map的node加上prev，next的reference
: insert 的时候，zturn, z-turn
: good luck
h*c
13 楼
估计可能要down tree,up tree,
你愿意折腾的话，还可以balance
你记住中数的reference的位置
前面插，移到next
后面插，移到prev
bst
有点忘了
regards
你愿意折腾的话，还可以balance
你记住中数的reference的位置
前面插，移到next
后面插，移到prev
bst
有点忘了
regards
g*k
14 楼
当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]，求区间
: 中位数
不过如果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
15 楼
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是非常困难的问题。
:
: .
其实那个tree map，只放一百个数就够了
可能３个就行
【在 g********k 的大作中提到】
: 当N很大时，找median其实很困难的，需要排序
: 不过如果distribution比较好（symmetric），可以用mean来代替。或者存一个table记
: 录区间内出现的个数，这个可以快速找到近似中位数（好处还是可以自己控制
: precision）
: 总之big data找median是非常困难的问题。
:
: .
g*k
16 楼
我不是google search scientist。。。
是我面试也遇到过这个问题（open ended，所以没有正确答案），不过我不懂binary
tree怎么解，你能具体讲讲嘛，我不是CS科班的。
【在 h**********c 的大作中提到】
: You are right, you are the best google search scientist. sincerely.
: 其实那个tree map，只放一百个数就够了
: 可能３个就行
是我面试也遇到过这个问题（open ended，所以没有正确答案），不过我不懂binary
tree怎么解，你能具体讲讲嘛，我不是CS科班的。
【在 h**********c 的大作中提到】
: You are right, you are the best google search scientist. sincerely.
: 其实那个tree map，只放一百个数就够了
: 可能３个就行
h*c
17 楼
想法不太成熟
不是记录一个中间数，而是纪录一个中间段
来的大数，小数都不进中间段
但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
凑合
这样不用对整个interval 排序
如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
【在 g********k 的大作中提到】
: 我不是google search scientist。。。
: 是我面试也遇到过这个问题（open ended，所以没有正确答案），不过我不懂binary
: tree怎么解，你能具体讲讲嘛，我不是CS科班的。
不是记录一个中间数，而是纪录一个中间段
来的大数，小数都不进中间段
但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
凑合
这样不用对整个interval 排序
如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
【在 g********k 的大作中提到】
: 我不是google search scientist。。。
: 是我面试也遇到过这个问题（open ended，所以没有正确答案），不过我不懂binary
: tree怎么解，你能具体讲讲嘛，我不是CS科班的。
h*c
18 楼
我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
数据还是很bias的话，还是问题
【在 h**********c 的大作中提到】
: 想法不太成熟
: 不是记录一个中间数，而是纪录一个中间段
: 来的大数，小数都不进中间段
: 但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
: 凑合
: 这样不用对整个interval 排序
: 如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
数据还是很bias的话，还是问题
【在 h**********c 的大作中提到】
: 想法不太成熟
: 不是记录一个中间数，而是纪录一个中间段
: 来的大数，小数都不进中间段
: 但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
: 凑合
: 这样不用对整个interval 排序
: 如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
h*c
19 楼
数据很bias 的话，可以preprocess 中间段个数，
或preprocess 若干个数，以免中间段完全左倾活右倾或
差不多了，
道数
道数
【在 h**********c 的大作中提到】
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 数据还是很bias的话，还是问题
或preprocess 若干个数，以免中间段完全左倾活右倾或
差不多了，
道数
道数
【在 h**********c 的大作中提到】
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 数据还是很bias的话，还是问题
g*k
20 楼
这个是可行的，但是如何确定中间段呢，如果来的data比较大，需要中间段移动很大的
话，就不好了。所以worst case还是需要排序的。
【在 h**********c 的大作中提到】
: 想法不太成熟
: 不是记录一个中间数，而是纪录一个中间段
: 来的大数，小数都不进中间段
: 但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
: 凑合
: 这样不用对整个interval 排序
: 如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
话，就不好了。所以worst case还是需要排序的。
【在 h**********c 的大作中提到】
: 想法不太成熟
: 不是记录一个中间数，而是纪录一个中间段
: 来的大数，小数都不进中间段
: 但中间段要移动（是个大问题），但近似的话中间段用一个tree map，在一定条件下还
: 凑合
: 这样不用对整个interval 排序
: 如果新来的数在中间段，进中间段，把中间段的最大或最小挤掉
g*k
21 楼
对，我说的也是这个，如果遇到bad data，这个方法code起来很麻烦的。
道数
道数
【在 h**********c 的大作中提到】
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 数据还是很bias的话，还是问题
道数
道数
【在 h**********c 的大作中提到】
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 我再改一下， 如果中间段要移动的话，左面的缺，或右面的缺，可以用后面的候补道数
: 数据还是很bias的话，还是问题
h*c
22 楼
如果bad data，cache 若干段
mix bias段with non-bias 短
preprocess
【在 g********k 的大作中提到】
: 对，我说的也是这个，如果遇到bad data，这个方法code起来很麻烦的。
:
: 道数
: 道数
mix bias段with non-bias 短
preprocess
【在 g********k 的大作中提到】
: 对，我说的也是这个，如果遇到bad data，这个方法code起来很麻烦的。
:
: 道数
: 道数
相关阅读
下次买车看来一定是GS350了。有没有hybrid 或者electric convertible？刹车时轮胎有噪音新手请教换轮胎和wheel alignment换windshieldPickup 到底能做些什么？SUV加个roof rack 一般大概多少钱？问问这辆Mitsubishi Eclipse怎样？Truecar Price锈蚀的螺丝，有什么好办法松开？GX460 怎么样？买完车后dealer推销的package值得买吗？特嘶拉VS lexusSan Jose South 求推荐个喷漆的地方买了一年的新车，今天十字路口熄火动弹不了，大家帮我看看左前轮撞矮隔离墩，rim严重变形！明天上图。现在的车质量真是不行，方向盘都不能装在中间说一个免费查autocheck vin的地方2013 Dodge Avenger/Charger如何？[合集] 买了帕萨特SE 带天窗