由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求问一道MS面试题
相关主题
A家面试题请教个面试题:大数据求中值
一道巨常见的题一道面试题
哪位大写给说说 何时用 merge sort, 何时用 quick sort, 何时 heap sort问道面试题
问个google面试题问个amazon面试题
问个google面试题G面试题求解
heap sort的缺点是什么?和quick sort比问个大数据处理的面试题
BST合并的面试题再问一道题
~~~~~~~~问个G家的题~~~~~~~~~~~请教一道算法题
相关话题的讨论汇总
话题: heap话题: sort话题: billion话题: 数据话题: controller
进入JobHunting版参与讨论
1 (共1页)
a*******o
发帖数: 67
1
有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1
BILLION数据,要怎么办?
我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个
数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数
重新PARTITION
然后面试官貌似不满意
然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞
进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP
要求太大了。
这题还有什么其他好的方法吗?
s**x
发帖数: 7506
2
分段counting ?
比如每百万个分组统计,最后对要的组再细分。
c*****t
发帖数: 48
3
这题要考虑分布式那块的点吗?
可以先在每台机器本地排序取前1B的数据,如果不足1B就全取,记录下这1B数据的mean
然后再用quicksort,pivot的值可以取所有mean值里的mean
然后一直下去。。直到最后总共剩下1B数据
瞎想的

TOP1
HEAP

【在 a*******o 的大作中提到】
: 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1
: BILLION数据,要怎么办?
: 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个
: 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数
: 重新PARTITION
: 然后面试官貌似不满意
: 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞
: 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP
: 要求太大了。
: 这题还有什么其他好的方法吗?

z****s
发帖数: 409
4
一共有多少机器?每台大约存多少?每台内存多大?相互传输速率多少?
毛都不知道想个屌。
l*******g
发帖数: 82
5
我觉得,LZ是不是可以考虑Divide and conque排序,比如MergeSort,或者用类似
MapReduce的方式来处理。
浅见,不对不要见怪!
s*w
发帖数: 729
6
参见 M 马 N 道,赛马找前 K 的问题

TOP1
HEAP

【在 a*******o 的大作中提到】
: 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1
: BILLION数据,要怎么办?
: 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个
: 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数
: 重新PARTITION
: 然后面试官貌似不满意
: 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞
: 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP
: 要求太大了。
: 这题还有什么其他好的方法吗?

b****t
发帖数: 112
7
基本步骤无非是sort(per machine)和merge(external merge).
1) Sort
for each machine:
sort top 1 Billion
2) Merge
merge 1 * 10 Billion into 1 Billion
优化设计:并行处理。设立中央控制器。
效果:a. 不必每个机器都占用1 billion内存 b.并行处理, 节约时间
Assume there is one independent server as the sorting controller.
The controller does the external file merge.
On each machine:
while (true)
{
communicate with controller:
{
get current low boundary
upload sorted value to the controller to merge
empty local cached
}
sort
{
Sort for 5 minutes or preset intervals, only keep the value above the
latest low boundary
}
if done file scan, exit
}

TOP1
HEAP

【在 a*******o 的大作中提到】
: 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1
: BILLION数据,要怎么办?
: 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个
: 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数
: 重新PARTITION
: 然后面试官貌似不满意
: 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞
: 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP
: 要求太大了。
: 这题还有什么其他好的方法吗?

c***0
发帖数: 449
8
可以分配k个heap给100billon的数,使得每个heap的容量足以放在内存中。
heap的特性是,第m个的最大数小于m+1的最小数,这样遍历一遍所有数,有溢出的heap
就向上溢出给下一个heap。
最后统计所需要的1billon的heap总数就可以了
p****U
发帖数: 109
9
对每部机子bucket sort 然后合并sort的结果。100 billion 数据 如果都是int 的话
大约400g吧。 算算几部机器handle得到
w*******e
发帖数: 395
10
假设每个数据是4B的int,100B需要400GB的存储,假设一台server有8GB可用的memory
,需要50台机器,另外有一台机器做controller
每台机器用bucket sorting,分成100个bucket,每台机器把每个bucket内数据的个数
报给controller,controller可以决定那个1B数据的边界会落在哪个bucket内
然后每台机器在相应的bucket内继续划分100个bucket,重复上一步,直到找到所有1B
数据为止。

TOP1
HEAP

【在 a*******o 的大作中提到】
: 有100BILLION的数据分散存储在很多机器中,各个机器都没有SORT, 现在要得到其TOP1
: BILLION数据,要怎么办?
: 我大概回答了一个像QUICK SORT一样的方法,选一个RANDOM的数,然后所有机器对这个
: 数PARTITION,然后如果根据结果对大于或者小于这个数的那部分数据,找一个新的数
: 重新PARTITION
: 然后面试官貌似不满意
: 然后我说了用一个HEAP储存TOP 1BILLION的数据。。然后有新数据比HEAP最小的小就塞
: 进去。。还是不行。。这个我后来想想确实觉得也不行,因为存储1BILLION数据的HEAP
: 要求太大了。
: 这题还有什么其他好的方法吗?

z****e
发帖数: 54598
11
re这个,我也是这么想的
不过我一般不叫这个controller,而叫master

memory
1B

【在 w*******e 的大作中提到】
: 假设每个数据是4B的int,100B需要400GB的存储,假设一台server有8GB可用的memory
: ,需要50台机器,另外有一台机器做controller
: 每台机器用bucket sorting,分成100个bucket,每台机器把每个bucket内数据的个数
: 报给controller,controller可以决定那个1B数据的边界会落在哪个bucket内
: 然后每台机器在相应的bucket内继续划分100个bucket,重复上一步,直到找到所有1B
: 数据为止。
:
: TOP1
: HEAP

1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一道算法题问个google面试题
Groupon电面heap sort的缺点是什么?和quick sort比
一个NxN矩阵每行每列都sort好,如何排序?BST合并的面试题
问个经典问题的improvement~~~~~~~~问个G家的题~~~~~~~~~~~
A家面试题请教个面试题:大数据求中值
一道巨常见的题一道面试题
哪位大写给说说 何时用 merge sort, 何时用 quick sort, 何时 heap sort问道面试题
问个google面试题问个amazon面试题
相关话题的讨论汇总
话题: heap话题: sort话题: billion话题: 数据话题: controller