kin*_*uk4 6 algorithm data-structures
我最近在与某家公司的访谈中遇到了这个面试问题.我试图使用maxHeap并试图解决它,但是他不能接受,因为问题陈述要求我在恒定的时间和恒定的空间内解决我.
因此,我认为有一些与魔法有关的东西,我想到了布隆过滤器,但正如我们在布隆过滤器中所知,我们可以简单地检查是否已经访问过特定的IP,它也可以返回误报.
任何人都可以帮我解决这个问题.面试结束了,但我仍然想了解如何特别对待IP,以便解决方案在时间和空间上都是O(c).
我假设您实时读取流，保留该流的最后 N 个地址，并在每次询问时返回此 N 元素缓冲区中最常见的 k 个。
为此，您需要两个数据结构：FIFO 和二叉树。FIFO 用于跟踪哪个地址离开缓冲区。
对于每个新地址：将其添加到带有计数器 1 的二叉树（如果不存在）或递增匹配计数器。以同样的方式从树中删除离开地址。
FIFO 操作的复杂度为 O(1)。二叉树运算的复杂度为 O(log N)，且 N 为常数。