Below is the implementation using HashMap and PriorityQueue

package Amazon; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.PriorityQueue; public class TopHotQueries { class Query { String query; int count; public Query(String query, int count) { this.query = query; this.count = count; } } private Map<String, Query> map; private PriorityQueue<Query> pq; private static final int LIMIT = 3; public TopHotQueries() { map = new HashMap<>(); pq = new PriorityQueue<>(LIMIT, new Comparator<Query>() { @Override public int compare(Query q1, Query q2) { return q2.count - q1.count; } }); } private Query insertToMao(String queryStr) { Query query; if (map.containsKey(queryStr)) { query = map.get(queryStr); } else { query = new Query(queryStr, 0); } query.count = ++query.count; map.put(queryStr, query); return query; } private List<Query> getTopK() { List<Query> queryList = new ArrayList<>(); PriorityQueue<Query> hotPQ = pq; int counter = 0; while(!hotPQ.isEmpty()) { queryList.add(hotPQ.poll()); ++counter; if(counter == LIMIT) { break; } } return queryList; } private void insertToPQ(Query prevQuery, Query curQuery) { if (null != prevQuery) { pq.remove(prevQuery); } if (pq.size() == LIMIT) { if (pq.peek().count < curQuery.count) { pq.poll(); } } pq.add(curQuery); } public void insert(String queryStr) { Query prevQuery = map.get(queryStr); Query curQuery = insertToMao(queryStr); insertToPQ(prevQuery, curQuery); } public static void main(String[] args) { // TODO Auto-generated method stub TopHotQueries thq = new TopHotQueries(); thq.insert("tablet"); thq.insert("kindle"); thq.insert("mac"); thq.insert("earpod"); thq.insert("books"); thq.insert("tablet"); thq.insert("earpod"); thq.insert("kindle2"); thq.insert("tablet"); thq.insert("tablet1"); thq.insert("tablet2"); thq.insert("tablet"); thq.insert("mac"); thq.insert("earpod"); thq.insert("mac"); for(Query top : thq.getTopK()) { System.out.println(top.query + " : " + top.count); } } }