hcallen.wang
BAN USERYou'll need a complex data structure, more likely a Most Used Cache.
To do this, you need to define a new class to simulate the cache, a hash table to record id, and a max heap to function as your actual cache.
Class looks like this:
class Node{
int id; //id
int r_t; //Retrieve times
Node prev, next; //previous and next node
}
The cache basically performs the following:
If incoming id hasn't appeared in heap (Use Hash Table to retrieve)
Add it to Hash Table;
Create new Node(id, r_t=1)
Insert node into heap;
else
Delete node from heap;
Increment r_t by retrieving Hash Table using key=id;
Re-insert node into heap;
Note: the insert(Node n) and delete(Node n) operations have to be considered properly performed at any position in heap.
Since max heap keeps r_t in descending order, once you update r_t and re-insert the node, the heap will automatically put it into right position. To accomplish this, you can choose either to design your own heap, or to use PriorityQueue in built-in library. After importing all incoming data stream into your heap, in which the first 10 elements is your top 10 data.
I assume both timestamps and ip address are represented in string.
All you need to do is create a Hash Table.
- hcallen.wang February 29, 2016