这是我最近收到的一个面试问题。这可能与一些我没有太多经验的前端Web开发有关。
问题是“您如何计算网站在过去 5 分钟内收到的访问次数”？
/* 好吧，根据评论和反对票，我决定写更多我/我朋友的想法。我目前的解决方案是构建一个存储访问时间戳的队列。给定一次新访问，我会在 5 分钟前删除所有访问，然后添加此新访问。但这似乎效率不高1）删除队列前面的元素效率不高，2）队列的长度与访问次数一样长。*/
面试官要代码，我不知道。
任何建议/意见表示赞赏！
问问题
90 次
1 回答
1
免责声明：由于您有兴趣了解问题和可能的解决方案，因此我不会添加任何代码，只是一些想法，您可以（并且应该）考虑它并在之后编写自己的代码。
一个细节可能会对您存储数据的方式产生影响：您的“分钟”粒度是多少？只是一分钟，是 60 秒还是 60,000 毫秒？例如，假设您当前的时间戳是 03:44:30,820。03:39:31,820 收到的请求是否发生在“最后 5 分钟”内？如果您的“分钟”粒度是一分钟，则不是（仅在 03:44、03:43、03:42、03:41 和 03:40 请求）。如果您的“分钟”粒度为 60 秒，则它确实发生在最后 5 分钟内。
因此，假设您的“分钟”粒度为 1 分钟（为简单起见）。这样，您的“队列”只有 5 个位置长。每个位置都可以包含在那一分钟内发生的请求计数。你的问题 #2 结束了。此外，如果你有一个链表而不是队列，你可以维护一个head和一个tail指针，也摆脱了你的问题 #1。
一个可能的优化（如果几分钟没有任何请求，可能会使代码复杂一点，但无论如何值得探索）是：由于您的列表具有固定大小（在本例中为 5），您也可以使用循环缓冲区，摆脱你的一对指针，只保留一个last指针。
这些只是一些想法，但面试官的意图可能是让你思考问题，提出一些问题，抛出一些想法，然后从中得出一些代码。
于 2013-04-23T18:55:55.320 回答