How to write customer equalsTo/compareTo/hasCode for TreeMap to get Top N values

Question

The question is:
Clients want to see which items are most sold so far. We want to provide this data to our clients efficiently.
Sample input:
List of sold items:
F|400
B|1000
A|500
A|600
C|1000
D|700
E|300
Sample output
A|1100
C|1000
B|1000
D|700

My thought is in first API processInput(), use a map of item and value to track all items sold so far and then add the updated item into a max priority queue. And in second API processQuery(), just select top K from queue. One issue is in processQuery, time complexity is O(NlogN).

Is it possible we solve this problem with a single TreeMap by overriding equalsTo, 'compareTo, and hasCode so that that treemap is sorted by value. So we just iterate over the TreeMap and return topN items?

Answer 1

You need efficient access in both directions: when items come, you need to get the aggregated amount based on their name (A,B,C), but for sorting them, the aggregated amount is going to be used. I think you could use a Map for finding items by name, and a SortedSet for sorting. As amounts themselves are not unique (like B and C have both 1000 in the example), sorting should also make use of the name (as those are unique), and that's why a set is enough for that part:

import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;

public class Test {
    static class Item implements Comparable<Item> {
        final String name;
        int amount;
        Item(String name,int amount){
            this.name=name;
            this.amount=amount;
        }
        public int compareTo(Item o) {
            if(o.amount<amount)
                return -1;
            if(o.amount>amount)
                return 1;
            return o.name.compareTo(name);
        }
        public String toString() {
            return name+"|"+amount;
        }
    }
    
    Map<String,Item> itemmap=new HashMap<>();
    SortedSet<Item> sorted=new TreeSet<>();
    
    void add(String name,int amount) {
        Item i=itemmap.get(name);
        if(i!=null) {
            sorted.remove(i);
            i.amount+=amount;
        } else {
            i=new Item(name,amount);
        }
        itemmap.put(name,i);
        sorted.add(i);
    }
    public static void main(String[] args) {
        Test t=new Test();
        t.add("F",400);
        t.add("B",1000);
        t.add("xA",500);
        t.add("xA",600);
        t.add("C",1000);
        t.add("D",700);
        t.add("E",300);
        System.out.println("itemmap: "+t.itemmap);
        System.out.println("sorted: "+t.sorted);
    }
}

It produces the output (test on Ideone: https://ideone.com/2d79aC)

itemmap: {B=B|1000, C=C|1000, D=D|700, E=E|300, F=F|400, xA=xA|1100}
sorted: [xA|1100, C|1000, B|1000, D|700, F|400, E|300]

I deliberately renamed A to xA, otherwise the map would be A|1100, B|1000, C|1000, but that's just a coincidence of alphabetical order (hashing a few consecutive, single-letter strings does not really mix the order). C and B come in this reverse order because that's what you have asked for. If you want them as B, then C, swap the compareTo(), or just return the current one with a negative sign.