讨论一道面试题啊(take home task)

查看 32|回复 1
作者:wangpugod2003   
题目很简单,就是一个文件,里面的数据就是 ID->value:
[u]  
例如:
123131321   100
135235423   101
132523121    80
...
给定一个值 n ,返回最大的 n 个值的 ID:
比如上面 n=2 ,就应该返回:
135235423   
123131321   
就是个 top k 的问题,也不要求返回的 id 的顺序。唯一的要求是这个文件极端的大。
我理解单个文件,哪怕几百 G 吧,我直接 java 中按照 BufferedReader 一行行的读,再用 size 为 n 的 PriorityQueue 梳理一遍整个[i]value>即可,时间复杂度就是 O(lines * logn)。
也写了单元测试+集成测试,各种不合法的 corn case 都处理了,生成了个 10G 的文件(几十亿条)测试了就一分多钟就出来结果。不知道怎么提交上去还是挂了。。
大家觉得应该用啥高级些的算法么?
zhy0216   
size 为 k 就够吧 每一个和最小的比较 大才进这个堆
您需要登录后才可以回帖 登录 | 立即注册

返回顶部