我目前正在准备一次面试,这让我想起了之前一次面试中被问到的一个问题,大致如下:
“你被要求设计一些软件,以持续显示 Google 上前 10 个搜索词。你可以使用提供无限实时流的数据源,该数据源提供当前正在 Google 上进行搜索的搜索词。请描述您将使用哪些算法和数据结构来实现此功能。您需要设计两个变体:
(i) 显示自开始阅读流以来的所有时间内排名前 10 的搜索词。
(ii) 显示过去一个月内每小时更新的前 10 个搜索词。
您可以使用近似值来获得前 10 名列表,但必须证明您的选择。”
我在这个面试中失败了,至今仍不知道如何实现。
第一部分要求在一个无限增长的子序列中找出前 10 个最频繁的元素。我研究了一些选择算法,但找不到任何在线版本来解决这个问题。
第二部分使用有限的列表,但由于处理的数据量很大,您无法真正将整个月的搜索词存储在内存中并每小时计算一次直方图。
由于前十列表一直在不断更新,所以问题变得更加困难,您需要通过滑动窗口计算出前十名的结果。
有什么想法吗?
你序列中子序列[2; 2; 3; 3; 3; 4; 4; 4; 4; 5; 5]中最频繁的项是什么?
- IVlad