首页 > 试题广场 >

有10个文件，每个文件1G，每个文件的每一行存放的都是用户的

[问答题]
有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序10个文件中的所有query。
添加回答
SkyWatcher头像 SkyWatcher
分别扫描10个文件，取key = hash(query)，key % 100将10G的query分配到100个文件中，从而保证不同的query一定在不同文件。扫描100文件，添加到map(key，nums)统计key出现的次数并排序。如果query重复率不高，则根据内存情况（比如1G）分别统计[10n, 10(n+1)](n∈[0-10])然后排序，最后对10个文件进行归并排序即可。
发表于 2015-09-20 16:43:16 回复(1)
Cplo头像 Cplo
1 hashtable到另外10个文件中（hash(query)%10），可以保证相同query进入同一文件；
2 分别求出10个文件的前10个频度的query，求最大建立大小为10的最小堆（反之建立最大堆）；
3 对筛选的100个query再次建立大小为10的堆，找出最终结果。
发表于 2015-09-14 16:05:42 回复(1)
提交观点

问题信息

美团 海量数据 排序
上传者：rootevil0
难度：
2条回答 18217浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号