分享一道昨天的面试题

上周遇到恶意刷流量，自己手动分析服务器日志（文件几百兆）找出可疑 IP，用的是传统命令行工具，比如：

$ shuf -r -i 1-100 | head -n 1000000 | sort | uniq -c | sort -n -r | head -n 10
10293 99
10286 18
10248 41
10220 16
10214 52
10202 81
10201 74
10180 30
10177 50
10168 42

定义个数组key为url，值为出现次数，逐行读取，然后统计。这么大的文件反正是不可能直接读入内存的

我的方案如下，有不对的地方还忘指正。 内存不能用，那就用硬盘。准备一个url统计文件夹，逐行读取日志中的url，然后以url命名在该文件夹中生成文件（如果过长可切割为缺省域名和get参数的url）,内容为1。相同url累加文件内容数量。统计结束后，遍历所有新生成的url文件和其余文件比较取出最大然后删除该文件，重复取出10个。

这个问题应该是分成两个部分：

1. 如何存储（会涉及到如何查找，没有则新增）
2. 如何排序（？？）

这应该是一个典型的数据结构和算法的问题。可以用树的数据结构。

每一个url都可以分解成几段：

1. https
2. www
3. baidu
4. com
5. 8080
6. mp3/id

然后把每一段都用一个int值表示，这样每一个网址就变成了一个int的序列[2,5,7,8,9,10]，这个序列中int的数量是可变的，有的网址的多一些，有的少一些。

接下来就可以根据这些序列的集合生成一颗树，树的路径对应的是url的路径，树的叶子对应的就是这个url的访问数量。

再然后就是找出10片最大的叶子了。

具体怎么做我也不会，只是提供个思路。欢迎讨论。

TopN问题啊，第一个想到的解法不应该是大小堆么，不过我上次刷题还是两年前找工作的时候，现在暂时没法一下子写出代码来，你可以找找最大堆、最小堆相关的资料看看。