「趣题」分布式找出出现次数最多的url

某天某度给了这么一条面试题：有N台机器（例如100台），每台机器上有个数十G的文件，每个文件上是一行行的url，这些url是用户访问的记录。求出所有机器中出现次数最多的url及其出现次数。

我想都没想就说用MapReduce说这是一个word count的过程，但是面试官不爽，说太慢了而且传输数据量极大。于是我又说不管怎样在最坏情况下都需要传输所有数据一遍的（例如没有重复的url的情况下。。），面试官说不行，他们想了个方法是可以不全部传输的。于是到最后我都没想到他想要的答案。。

后来，通过和cc等同学讨论，我想面试官想说的是，不管在什么情况下，在保证答案正确的前提下（不是近似值，即普通的去掉长尾的方法是不行的），让能传输的数据量尽量最少。如果是这样就有一个比较明显的剪枝方法，可以这样做：

1. 首先把每台机器中相同的url合并在一起
2. 把每台机器排名前k位（可以简单地取为1）的url分别发到所有其他机器中，最后合并得到每台机器排名前k位的url（一共M个）的全局计数（如果所有这些前k位的url都不相同，那么最多有M=N⋅k个url），然后把这些url从每台机的排名中删除
3. 如果当前（删掉第2步中那些topk的url之后）所有机器排名最高的url的计数加起来（注意不要求它们是相同的url）都小于当前得到的全局计数最多的url的计数，则结束，否则继续第二步

这个算法我目测是正确的，以后有空的时候再来证明一下。而且根据现实生活中的长尾效应，不需要计算太多轮就能找到出现次数最多的url了，且不用传输所有url，又没使用近似值，也许这就是面试官要的答案吧。不知道有没别的剪枝方法比这个更好。

[2016/11/14补充]

其实哈希一下，只传64位的哈希值做word count，找到次数最多的哈希，然后再读一遍源文件找出该哈希对应的url，行不行？