扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 海量数据高频面试题 > 1.海量日志数据,提取出某日访问百度次数最多的那个IP

题目的隐藏含义就是海量日志数据不能一次读取到内存中,否则直接用HashMap统计IP出现的频率(IP为key,频率为Value),然后按照频率排序就好了。

这道题的做法是先对文件遍历一遍,将一天访问百度的IP记录到一个单独的文件,如果这个文件还是很大,可以对IP进行hash取余,将IP映射到多个文件中,然后利用HashMap统计每个文件中IP的频率,分别找到每个文件中频率最高的IP,再从这些IP中找到整体频率最高的IP。

如果是频率最高的前N个怎么办?这时可以在利用HashMap统计每个文件中IP的频率后,维护一个小顶堆,找到TopN。具体方法是:依次遍历每个小文件,构建一个小顶堆,堆大小为 N。如果遍历到的IP的出现次数大于堆顶IP的出现次数,则用新IP替换堆顶的IP,然后重新调整为小顶堆,遍历结束后,小顶堆上的词就是出现频数最高的 N 个IP。

注:TopN问题在手写代码也是高频题,需要重点掌握,比如力扣215题:https://leetcode.cn/problems/kth-largest-element-in-an-array/comments/


点击面试手册,获取本站面试手册PDF完整版