Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

常见系统设计题系列-热门搜索TopK

问题:

从300万字符串中找到最热门的10条搜索的输入信息是一个字符串,统计300万输入信息中的最热门的前10条,我们每次输入的一个字符串为不超过255byte,内存使用只有1G。请描述思想,写出算法(c语言),空间和时间复杂度。

答案:

300万个字符串最多(假设没有重复,都是最大长度)占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。

可以使用key为字符串(事实上是字符串的hash值),值为字符串出现次数的hash来统计每个字符串出现的次数。

并用一个长度为K的堆来的数组/链表存储目前出现次数最多的10个字符串。

你的支持是我坚持的最大动力!