我正在准备接受采访,这让我想起曾经在之前的一次采访中被问过的一个问题:
"您被要求设计一些软件,以便在Google上连续显示前10个搜索字词.您可以访问提供无限实时搜索字词流的Feed,目前正在Google上搜索.请说明算法和数据结构你会用来实现这个.你要设计两个变种:
(i)显示所有时间的前10个搜索词(即自您开始阅读提要以来).
(ii)仅显示过去一个月的前10个搜索字词,每小时更新一次.
您可以使用近似值来获得前十名,但您必须证明自己的选择是合理的."
我在这次采访中遭到轰炸,但仍然不知道如何实现这一点.
第一部分要求在无限列表的不断增长的子序列中的10个最频繁的项目.我查看了选择算法,但找不到任何在线版本来解决这个问题.
第二部分使用有限列表,但由于处理的数据量很大,您无法将整个月的搜索项存储在内存中并每小时计算一次直方图.
前十名列表不断更新,这个问题变得更加困难,所以不管怎样你需要在滑动窗口上计算前十名.
有任何想法吗？