一个Web服务器可以接收数百万个用户登录请求。一个用户可以多次登录。设计一种最优算法/数据结构来返回在给定时间间隔内唯一用户的总数,以时间复杂度为考量。
例如:计算t1和t2之间以及t2和t3之间的唯一用户总数。同时考虑重叠时间间隔的总数(t1 = 10am,t2 = 10:15am,t3 = 10:30am,在10:10am到10:20am之间返回用户总数)。
以下是我提出的方案,请大家评论:
我认为使用哈希映射和最小堆的组合是一个好的最优解。
哈希映射 - 键为用户ID,值为指向最小堆中相应节点的节点指针。 最小堆 - 最后登录时间作为键,用户ID作为值。根将是登录时间最早的用户。还要在根节点存储最小堆中节点总数的计数,以便我们可以快速返回计数。
1.当用户登录时。使用用户ID作为键在哈希映射中查找。 a) 如果没有匹配,则将新用户插入哈希映射和最小堆中,并将计数增加到最小堆的根节点。 b) 否则,它是旧用户,更新其最后登录值,并且不要增加最小堆的根节点中的计数。
2.每当我们想要找出t2-t1之间登录的唯一用户时, a. 从堆中提取最小值(根),并检查 当前时间-最后登录时间> t2-t1分钟。如果大于 从哈希映射和最小堆中删除该值。 b. 重复上述步骤(a),直到堆的最小元素满足 当前时间 - 最后登录时间<= t2-t1分钟 c. 返回最小堆的根节点中的计数值。
但我无法确定重叠时间间隔的算法。
例如:计算t1和t2之间以及t2和t3之间的唯一用户总数。同时考虑重叠时间间隔的总数(t1 = 10am,t2 = 10:15am,t3 = 10:30am,在10:10am到10:20am之间返回用户总数)。
以下是我提出的方案,请大家评论:
我认为使用哈希映射和最小堆的组合是一个好的最优解。
哈希映射 - 键为用户ID,值为指向最小堆中相应节点的节点指针。 最小堆 - 最后登录时间作为键,用户ID作为值。根将是登录时间最早的用户。还要在根节点存储最小堆中节点总数的计数,以便我们可以快速返回计数。
1.当用户登录时。使用用户ID作为键在哈希映射中查找。 a) 如果没有匹配,则将新用户插入哈希映射和最小堆中,并将计数增加到最小堆的根节点。 b) 否则,它是旧用户,更新其最后登录值,并且不要增加最小堆的根节点中的计数。
2.每当我们想要找出t2-t1之间登录的唯一用户时, a. 从堆中提取最小值(根),并检查 当前时间-最后登录时间> t2-t1分钟。如果大于 从哈希映射和最小堆中删除该值。 b. 重复上述步骤(a),直到堆的最小元素满足 当前时间 - 最后登录时间<= t2-t1分钟 c. 返回最小堆的根节点中的计数值。
但我无法确定重叠时间间隔的算法。