我最近在一家公司的面试中遇到了这个问题。我尝试使用maxHeap并尝试解决它,但他不接受,因为问题陈述要求我在常数时间和常数空间内解决它。
所以,我认为与位操作有关,布隆过滤器浮现在我的脑海中,但正如我们所知,在布隆过滤器中,我们可以简单地检查特定IP是否已被访问,但它也可能返回假阳性。
请问有人能帮我解答这个问题吗?面试已经结束了,但我仍然想了解如何将IP地址特殊处理以使解决方案在时间和空间上都是O(c)。
我最近在一家公司的面试中遇到了这个问题。我尝试使用maxHeap并尝试解决它,但他不接受,因为问题陈述要求我在常数时间和常数空间内解决它。
所以,我认为与位操作有关,布隆过滤器浮现在我的脑海中,但正如我们所知,在布隆过滤器中,我们可以简单地检查特定IP是否已被访问,但它也可能返回假阳性。
请问有人能帮我解答这个问题吗?面试已经结束了,但我仍然想了解如何将IP地址特殊处理以使解决方案在时间和空间上都是O(c)。
这可以肯定地在常数时间内完成,但空间复杂度不是常数。您需要的空间与迄今为止遇到的唯一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.
实际上,分配一个大小为2 ^ 32的数组是常数空间,所以您只需分配该数组,在读取流时将1添加到每个IP读取的array [IP]中,然后只需对数组进行排序( CONSTANT时间, O(32 * 2 ^ 32)!),然后选择前k个地址。 Voila,常数时间,常数空间。效率低下,但问题没有要求效率!