Best Data Structure for fast retrieval, update, and keeping ordering

Question

The problem is as follows

• I need to keep track of url + click count.
• I need to be able to update url quickly with click count when user click on that url.
• I need to be able to retrieve the top 10 click count URL quickly.

NOTE: Assuming you cannot use the database.

What is the best data structure to achieve the result?

I have thought about using a map before, but map doesn't keep track of ordering of the top 10 clicks.

Answer 1

You need an additional List<Map.Entry<URL,Integer>> for holding the top ten, with T being the click count for the lowermost.

• If you count another click and this count is still not greater than T: do nothing.
• If the increased count is greater than T, check whether the URL is in the list or not. If it is, do nothing. If it is not, add this entry to the List, sort and delete the last entry if the list has more than 10 entries. Update T.

Answer 2

The best data structure I can think is of using the TreeSet.

The elements of TreeSet are sorted, so you can easily find top items. Also make sure for URL you maintain a separate comparator class which implements Comparator, so you can put your logic of keeping elements sorted all the time based on count. Use this comparator while creating the TreeSet. Insertion/Update/delete/Get all operations happen in O(logn)

Here is the code, how you should define the structure.

 TreeSet<URL> treeSet = new TreeSet<URL>(new URLComparator());


class URL {
    private String url;
    int count;

    public URL(String string, int i) {
        url = string;
        count = i;
    }

    @Override
    public int hashCode() {
        return url.hashCode();
    }

    @Override // No need to write this method. Just used it for testing 
    public String toString() {
        return "url : " + url + " ,count : " + count+"\n";
    }

}

One more info- Use hashcode method of your URL class as hashcode of your url.

This is how you define URLComparator class. compare logic is based on URL count.

class URLComparator implements Comparator<URL> {

    @Override
    public int compare(URL o1, URL o2) {
        return new Integer(o2.count).compareTo(o1.count);
    }

}

Testing

TreeSet<URL> treeSet = new TreeSet<URL>(new URLComparator());

treeSet.add(new URL("url1", 12));
treeSet.add(new URL("url2", 0));
treeSet.add(new URL("url3", 5));

System.out.println(treeSet);

Output:-

[url : url1 ,count : 12
, url : url3 ,count : 5
, url : url2 ,count : 0
]

To print top 10 elements, use following code.

Iterator<URL> iterator = treeSet.iterator();
int count = 0;
while(count < 10 && iterator.hasNext() ){
    System.out.println(iterator.next());
    count++;
}