algorithm - 实时获取网站排名信息

Question

我在采访中遇到了这个问题。

假设我们有用户访问网站的日志信息，这些信息包括网站、用户、时间。我们需要设计一个数据结构，我们可以得到的信息

• 特定网站的前五名访问用户
• 特定用户访问前五名的网站
• 一天仅访问 100 次的网站

全部实时

我第一个想到的是，我们可以直接用一个数据库来存储日志，每次只需要对每个用户或者每个网站进行统计和排序即可。但这不是实时的，因为我们需要进行大量计算才能获取信息。

然后我觉得我们可以针对每个问题使用HashMap。例如，对于每个网站，我们使用 HashMap<Website, <TreeMap<User, count>> ，这样我们就可以获得特定网站的前五名访问者。但是面试官说三个问题我们只能用一种数据结构，因为第二个问题会用HashMap<User, <TreeMap<Website, count>>。 ，具有不同的键和值类型。

有人能想出解决这个问题的好方法吗？

Answer 1

map 的 map ，具有通用类型，作为基本方法。

第一个 map 代表全局数据结构，它将包含三个问题的 map 。

第一个内部 map ，您将网站作为关键字和前 5 位用户的列表。

第二个内部 map ，您将以用户为键，并列出他访问过的前 5 个网站。

对于最后一个问题，您可以在第三个内部 map 上以网站为键，访问者数量为值。

如果他们的意思是针对三个不同的问题使用相同的数据结构，那么请不要忘记全局 map 。

如果您想更深入一点，可以考虑使用邻接矩阵实现，其中您的用户和网站标识是您的列/行标识符，值是访问者的数量。