algorithm - 存储有关在 d 天访问过 w 网页的 u 客户数据的好方法

Question

这是亚马逊的面试问题。

给定 u 个在 d 天访问过 w 网页的客户列表，设计一个数据结构来获取在 d 天访问过该网站的客户恰好 k 天并且应该总共访问了至少 m 个不同的页面。

假设 u、w 和 d 是大数。

我们如何存储这些信息？也许我们可以使用 HashMap 、树等。

Answer 1

假设:

我们有一些查询，它给出一些网页 j 并要求提供恰好在 k 天访问过该网页并且至少访问过 的用户列表总共 >m 个不同的页面。

对于下面的内容，假设“map”=“hashmap”，理想情况下，它会给出恒定时间查询。人们还可以以元素数量的对数成本使用“treemap”。对于“set”、“hashset”、“treeset”也是如此。

我假设输入不是静态的，但如果它是静态的，我不会真正改变我的方法。

基本思路:

• 对于每个用户，都有一个要计算的网页 map 和上次访问日期。我们可以将用户标识符映射到网页映射。

• 每当用户访问页面时:

  • 如果是新页面，只需创建一个 map 条目，页面计数为 1，最后访问日期

  • 否则，如果当天与上次访问的日期相同，则什么也不做，

  • 否则，增加计数并更新最后访问的日期。

  • 每次更新的总时间 = O(1)

• 查询:

  • 遍历所有用户 - O(u)

  • 查找该用户的页面并检查计数是否匹配 - O(1)

  • 检查 map 的计数是否为 >= m - O(1)

  • 每次查询的总时间 = O(n)

改进:

我们可以有一个单独的网页映射到唯一 ID(然后显然使用唯一 ID 而不是上面映射的 URL)。它不会真正改变复杂性，但应该以常数因子提高空间和时间复杂性。

以相当大的空间为代价，我们可以执行以下操作(除了从 Basic idea 中获取 map ):

• 对于每个网页，都有一个用户标识符集数组，其中数组中的索引 i 是访问该页面的所有用户的集合恰好 i 天。

• 每当用户访问页面时:

  • 与基本思路

    中的操作相同

  • 将用户从该页面的当前访问次数移动到新的访问次数(如果是新的，则插入到 1 次访问集中)。

  • 每次更新的总时间 = O(1)

• 查询:

  • 我们可以在 O(1) 中找到恰好在 k 天内访问任何给定页面的所有用户。

  • 从这里我们遍历这个较小的用户列表(假设有 p 个用户)并检查每个用户的 map 计数(在 O(1) 中).

  • 每次查询的总时间 = O(p)

如果我遗漏了什么，请随时指出。