在常数时间和常数空间内给出大量IP地址中最常见的k个IP地址

Question

我最近在一家公司的面试中遇到了这个问题。我尝试使用maxHeap并尝试解决它，但他不接受，因为问题陈述要求我在常数时间和常数空间内解决它。

所以，我认为与位操作有关，布隆过滤器浮现在我的脑海中，但正如我们所知，在布隆过滤器中，我们可以简单地检查特定IP是否已被访问，但它也可能返回假阳性。

请问有人能帮我解答这个问题吗？面试已经结束了，但我仍然想了解如何将IP地址特殊处理以使解决方案在时间和空间上都是O(c)。

- kinshuk4

---

一些有趣的Boyer-Moore多数投票算法的扩展？即使如此，这也需要存储整个流... - Nemo

使用布隆过滤器，您只能确定特定的IP地址是否已经被遇到，而问题需要找出最常访问的k个IP地址。 - discoverAnkit

@ankitG，我同意你的观点，这就是要点——它可以告诉我们是否遇到了IP，而且还有一定的概率p。已经得到了两个答案，正在努力理解它们。 - kinshuk4

@Nemo，我会阅读Boyer Moore多数投票算法 :)。谢谢。 - kinshuk4

你没有充分定义问题，以便我们提供答案。那个“大流”长度不确定吗？这是否应该实时完成，以便您可以检索自开始查看流以来看到的k个最常见的IP地址？还是在您到达流的末尾后只想获取k个最常见的IP地址？ - Jim Mischel

Answer 1

这可以肯定地在常数时间内完成，但空间复杂度不是常数。您需要的空间与迄今为止遇到的唯一IP地址数量成比例。

可以使用两个数据结构来完成此操作--

1.) 散列表

2.) 双向链表（也可以使用单向链表，但双向链表将更有效）

双向链表最多有'k'个节点。

struct DLL{

  string IPAddress;
  int count;
  struct DLL* next;
  struct DLL* prev;
}

哈希表中的键是IP地址。值将是一个元组<计数，双向链表节点地址>。

一旦IP地址从流中出现，就会在O(1)时间内在哈希表中进行检查。

if it's not present,    
   if number of nodes in the DLL is less than k, 
        add a new node at the start of the DLL for this IPAddress and a new
        entry is made in the hashtable <IPAddress,<count(=1 here),its    
        address in DLL>>
   else
        other IP Addresses in the DLL must be having a count of at least 1,
        so no point putting it in the DLL. Just add a new entry to the
        hashtable <IPAddress,<count(=1 here),null>
else
   update the tuple i.e increase the value of count by 1 and,
      if DLL node address is not NULL, 
        go to that node in the DLL, increase count there also and shift it 
        rightwards if at all count's value now is greater than
        next DLL node's count. Keep doing that till the concerned node
        reaches the right position. This is done in O(k). k is a constant as 
        per the problem statement. DLL really comes handy for these operations.
        We have to make sure that the DLL is always sorted in ascending order.
        Also, its very important to make the shifts by swapping links and not 
        by swapping values otherwise we end up updating the hash table for every
        which doesn't increase the time complexity but unnecessarily increases
        the number of operations
      else
        compare this IP Address's count with the count in the first node in DLL, if 
        its greater than the count of first node, create a new Node and insert 
        in the DLL appropriately in O(k). Update the hash table for this IP Address 
        and for the first IPAddress in the DLL before purging that node.

因此，这样做可以使得DLL中最常见的k个IP地址始终以恒定时间可用。

- discoverAnkit

---

谢谢您提供的方案。但他也提到了常数空间 :/. - kinshuk4

Answer 2

实际上，分配一个大小为2 ^ 32的数组是常数空间，所以您只需分配该数组，在读取流时将1添加到每个IP读取的array [IP]中，然后只需对数组进行排序（ CONSTANT时间， O（32 * 2 ^ 32）！），然后选择前k个地址。 Voila，常数时间，常数空间。效率低下，但问题没有要求效率！

- Vesper

---

我的想法也是如此。除非“IP地址”包括IPV6…… - Jim Mischel

@JimMischel 嘿嘿 :) 如果包括IPv6，这将不起作用，但是想要从整个IPv6池中获得前2^32的人的视角是...压倒性的。 - Vesper

Answer 3

我假设您实时阅读流，保留此流的最后N个地址，并在需要时返回这个N元素缓冲区中出现频率最高的k个地址。为此，您需要两种数据结构：FIFO和二叉树。FIFO用于跟踪哪个地址离开了缓冲区。对于每个新地址：如果不存在，则将其添加到二叉树中并计数为1，否则增加匹配计数器。同样地，以相同的方式从树中删除“离开”的地址。FIFO操作为O(1)。二叉树操作为O(log N)，其中N为常数。

- DrKoch

---

如题所述，该问题要求您的N等于无穷大。 - Nemo

我认为问题描述不完整。我猜测 OP 想要的是类似于“最近一小时内访问量最高的前十个 IP 地址”这样的东西，适用于高带宽页面。 - DrKoch

@DrKoch，我在尝试理解你的解决方案，N是什么？ - kinshuk4

请看我的回答的第一句话。那是FIFO缓冲区的长度。 - DrKoch