TopK 最大的K个数
10亿数据内筛选最大的100个，要求速度要快。
最近阿里的一道面试题，其实基于多层博弈论，我想我刷过这题，我知道如何偷鸡的。我以为我在第二层，没想到我只在第一层。
第一层
于大顶堆的方式的方式筛选出数组内最大的k个数。
先看看顶堆的数据结构，其中可以看出0位置是要么就是堆内最大或者最小，然后我们可以利用堆的特性，去把当前的数组的值和这个最大最小进行比较。堆的另外一个特性就是会重排序，参考堆排序算法。
当然你让我现场手写写我肯定是忘了，但是一个开发是可以偷鸡的呀，我们可以直接用优先级队列PriorityQueue的内部实现就是大顶堆。对于海量数据来说，优先级队列基本就是一个比较合适的答案了。
总数1万个取最大100，快排略快，最小堆偶尔快。
总数10万个取最大100，最小堆略快，快排偶尔快。
总数100万个取最大100，最小堆完胜，快排没戏，而且最小堆大概快了2倍。
总数1000万个取最大100，最小堆完虐，快排没戏，而且最小堆快了大概2倍。
结论：最小堆比快排优秀。
原因：
1.速度确实快。
2.最小堆不需要打乱原数据顺序，而快排会打乱。（并不是快的原因，而是最小堆的优点）
3.如果内存有限，无法加载所有数据，则最小堆快。
以上数据引用自 topK问题最小堆和快排哪个快。所以偷鸡就可以解决第一层的问题。
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue=new PriorityQueue<Integer>(k,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
for(int i=0;i<nums.length;i++){
queue.add(nums[i]);
if(queue.size()>k){
queue.poll();
}
}
return queue.peek();
}
这是我leetcode乱写的第k大个数啊。
第二层
面试官对我的偷鸡取巧并不满意啊，他需要我提速，这个速度不行啊。
What？？是有时间复杂度更低的吗？不不不，这是一道核心竟然是一道多线程的题目。
- 将10亿的数据分片，通过分治的思维对数据进行第一次处理。
- 开启多线程然后对其进行这些分片的数据进行优先级队列操作。
- 然后每个子线程筛选出其中最大的k个数
- 当所有线程执行完毕之后合并数据
我猜测的第三层
- 是不是考虑下多少个数据一分片，然后如何把效能提升到最高的问题？
- 构建多少个线程读取效率是最高的？
这个都是我没想到的，各位大佬有想法的可以聊一下啊。
一篇文章内的单词数量
这题乍一看卧槽貌似不难，foreach循环碰到一个空格或者标点的情况下sum++，是不是就可以解决这个问题。
然而事情并没有想想的这么简单。面试被问到这种问题最难的是什么，可能是对于这题目真实的边界问题的思考。
- 如果这篇文章内容很大怎么办，会不会把内存吃光？
- 如何给单词去除重复？
是不是可以考虑逐行读取呢？
将其转化成IO流，逐行读取流，之后对这个输入内容进行一次计数操作，是不是就可以解决这个问题呢。
单词重复的问题
卧槽，这个真简单HashSet啊！！！！那么如果海量数据我是不是又炸了？
卧槽，死亡螺旋吗。或许我们可以考虑下用hash的方式来解决，只保留单词的hashcode，是不是可能可以解决呢。
同样的这个也可以使用多线程分片去优化
方式的话基本也和上面是完全一样的，只要把数据分片，之后多线程调度，然后合并结果就可以了。
总结
我问了下后端大神，这些应该都是mapreduce里面出现的原题啊，都是和海量数据相关的，有兴趣的可以自己去查下。
别说了，这些都是下场之后想了想总结的，当场面试就是懵逼的，边界个锤子。
在这也推荐一份大佬自己收录整理的Android学习PDF+架构视频+面试文档+核心笔记（包含算法题整理哦），还有高级架构技术进阶脑图、Android开发面试专题资料，高级进阶架构资料帮助大家学习提升进阶，也节省大家在网上搜索资料的时间来学习，也可以分享给身边好友一起学习。
喜欢本文的话，不妨动动你可爱的小手指点个赞+转发呗~ 谢谢！！！需要领取资料的话简信信我【666】我发给你或者直接点击领取地址
网友评论