6

I recently came across this interview question in my interview with a particular company. I tried to use maxHeap and tried to solve it, but it was not acceptable to him, as the question statement asked me to solve me in constant time and constant space.

So, I thought there is something related to bit magic, and bloom filters came to my mind, but as we know in bloom filters we can simply check if particular IP has been visited or not and it can also return false positives.

Can anyone please help me with this question. Interview is over, but I still I want to understand how can IPs be treated specially so that solution is O(c) in time and space.

5
  • Some interesting extension of Boyer-Moore majority vote? Except even that requires storing the entire stream...
    – Nemo
    Commented May 10, 2015 at 15:07
  • With bloom filters, you can only be sure if a particular IP address has not been encountered whereas the problem demands k IP addresses which are most frequently visited. Commented May 10, 2015 at 19:13
  • @ankitG, I agree with you, that's the gist - it can tell whether the IP has been encountered or not, that to with some probability p. Got the 2 answers. Trying to understand them.
    – kinshuk4
    Commented May 26, 2015 at 14:39
  • @Nemo , will read Boyer Moore majority vote :). Thanks.
    – kinshuk4
    Commented May 26, 2015 at 14:40
  • You haven't defined the problem sufficiently for us to provide an answer. Is that "large stream" of indeterminate length? Is this supposed to be done in real time, so that you can retrieve the k most frequent IP addresses seen since you started looking at the stream? Or do you just want to get the k most frequent once you've reached the end of the stream? Commented Jun 1, 2015 at 14:24

3 Answers 3

2

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.

1
  • thanks for the solution. But he also mentioned constant space :/.
    – kinshuk4
    Commented May 26, 2015 at 14:44
2

In fact, allocating an array of 2^32 is constant space, so you just allocate that, read the stream adding 1's to the array[IP] for each IP read, then you just sort the array (CONSTANT time, mind you, O(32*2^32)!) and then select top k addresses. Voila, constant time, constant space. Inefficient, but the question did not ask for inefficiency!

2
  • 1
    My thought, too. Unless "IP addresses" includes IPV6 . . . Commented Jun 1, 2015 at 14:26
  • 1
    @JimMischel Hehe :) If IPv6 are included, this will not work, but the perspective of someone wanting top 2^32 out of whole IPv6 pool is... overwhelming.
    – Vesper
    Commented Jun 1, 2015 at 15:31
1

I assume you read the stream in realtime, keep the last N adresses of this stream and return the k most frequent of this N-element buffer whenever asked.

To do so you need two data structures: a FIFO and a Binary tree. The FIFO is used to keep track which adress leaves the buffer.

With each new address: Add it to the binary tree with counter 1 if not present or increment the matching counter. Remove the leaving address from the tree the same way.

FIFO Operations are O(1). Binary tree operations are O(log N) with N constant.

4
  • As stated, the problem wants your N equal to infinity.
    – Nemo
    Commented May 10, 2015 at 15:05
  • 1
    Well, I think the problem description is not complete. I guess what OP wanted is something like "Top 10 IPs in the last hour" for a high bandwith page
    – DrKoch
    Commented May 10, 2015 at 18:04
  • @DrKoch , I was trying to understand your solution, what is N?
    – kinshuk4
    Commented May 26, 2015 at 14:42
  • See the very first senzence of my answer. It is the length of the FIFO Buffer.
    – DrKoch
    Commented Jun 1, 2015 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.