This can be done in constant time for sure but not in constant space. You need space proportional to the number of unique IP addresses encountered so far.
This can be done using two data structures--
1.) A hashtable
2.) A doubly linked list(singly linked list can also be used but DLL will be more effective)
DLL will have at max 'k' nodes.
struct DLL{
string IPAddress;
int count;
struct DLL* next;
struct DLL* prev;
}
Key in the hashtable is the IP address. Value would be a tuple < count,address of Doubly Linked List Node>.
As soon as an IP address comes from the stream, it is checked in the hashtable in 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.
So, this way, k most frequent IP Addresses are always available in the DLL in constant time.