4

一个 Web 服务器可以接收数百万个用户的登录请求。一个用户可以多次登录。根据时间复杂度设计最佳算法/数据结构，以返回给定时间间隔之间的唯一用户总数。

例如：计算间隔 t1 & t2 和 t2 & t3 之间的唯一用户总数。还要考虑返回重叠间隔的总数（t1 = 10am，t2 = 10:15am，t3 = 10:30am，返回 10:10am 到 10:20am 之间的用户总数）

以下是我的建议，希望人们发表评论吗？

Hashmap 和最小堆的 IMO 组合将是一个最佳解决方案。

Hashmap-将键作为用户ID，将值作为指向最小堆中相应节点的节点指针。最小堆 - 最后登录时间作为键和值作为用户 ID。Root 将是登录时间最早的用户。同样在根存储最小堆中节点总数的计数，以便我们可以快速返回计数。

  1. 当用户登录时。以 user-id 作为键在 hashmap 中查找。a) 如果不匹配，则将新用户插入 hashmap 并将用户的新节点插入最小堆，并增加存储在最小堆根节点的计数。b) 否则它是一个老用户更新它的最后登录值并且不增加最小堆根节点中的计数。

  2. 每当我们想找出在 t2-t1 之间登录的唯一用户时，a. 从堆中提取 min(root) 并检查当前时间 - 最后登录时间 > t2-t1 分钟。如果大于从 hashmap 和 min_heap 中删除该值。湾。重复上述步骤(a)，直到堆的min元素满足当前时间-last-logged-in time <= t2-t1 mins c。从最小堆的根节点返回计数值。

但我无法确定重叠间隔的算法。

4

1 回答 1

1

我认为有一种更简单的方法可以做到这一点。考虑将所有数据存储在平衡二叉搜索树中，其中键是登录时间，值是当时登录的所有人员的列表（假设可以在完全相同的时间有多个登录） . 从那里，您可以找到所有在时间 T1 和 T2 之间的时间间隔内登录的人，方法是找到 BST 中时间大于或等于 T1 的最小节点，然后不断计算该节点的中序后继，直到您到达一个节点，它在时间严格地在时间 T2 之后。

在 BST 中查找大于或等于 T1 时间的第一个节点在平衡 BST 中需要时间 O(log n)，并且多次计算中序后继需要时间 O(k)，其中 k 为您报告的匹配总数。这总共需要 O(log n + k) 时间。由于您必须花费至少 O(k) 时间报告任何算法中的所有匹配登录，因此开销非常低。

或者，如果您从服务器获取流中的数据（即，随着时间的推移，新登录总是会发生），您可以只使用标准数组来保存所有请求。您可以将新请求附加到数组的末尾。由于时间总是向前移动，这意味着数组总是排序的，所以你可以使用二分查找来找到范围的起点。假设数据不是病态构造的，您还可以使用插值搜索来使查找时间预期为 O(log log n) 而不是 O(log n)，从而在查找 k 时给出预期的 O(log log n + k) 查找时间总元素。

至于处理重叠范围 - 有一些标准算法可以获取一系列范围并将它们合并到最少数量的非重叠范围中。在进行查找之前，您始终可以应用其中一种技术来处理这种情况。

希望这可以帮助！

于 2013-06-23T08:06:38.673 回答