Implemented Sorting of Map by Value and then by Key in java

Question

So I had this requirement to get the frequency of names appearing in a list and then print the one appearing the most number of times. If there is a clash, print the one which comes first in the dictionary

so if I had

{"john", "johnny", "jackie", "johnny", "john", "jackie", "jamie", "jamie", "john", "johnny", "jamie", "johnny", "john"}

the result should be john as john and johnny appear an equal number of times (4) but since john comes first in a dictionary, the result is john.

Please suggest how can I make this code better.

public class Solution {
 public static void main(String[] args) {
 String[] votes = {"john", "johnny", "jackie", "johnny", "john", "jackie", "jamie", "jamie", "john", "johnny", "jamie", "johnny", "john"};
 System.out.println(findWinner(votes));
 }
 private static String findWinner(String[] votes) {
 //create a frequency map
 Map<String, Long> map = Arrays.stream(votes).collect(Collectors.groupingBy(Function.identity(), HashMap::new, Collectors.counting()));
 //comparator that sorts by value then by key
 Comparator<Map.Entry<String, Long>> comparator = (o1, o2) -> {
 int val = o2.getValue().compareTo(o1.getValue());
 if (val != 0)
 return val;
 else
 return o1.getKey().compareTo(o2.getKey());
 };
 //create a list of entries to be sorted
 List<Map.Entry<String, Long>> list = new ArrayList<>(map.entrySet());
 //sort the list
 list.sort(comparator);
 //return the first element of the sorted list
 return list.get(0).getKey();
 }
}

• TorbenPutkonen: Can you elaborate on why you wrote this code? It looks like it could be either home work or for a job interview, but those two have very different reviewing standards. If it's home work, please explain what was the subject of the class in question.
• Janardhan Maithil: This is just for learning purposes. Trying out my hand on comparators. Wanted to check if there is any better way to solve the problem

Answer 1

You'd help yourself hugely by picking the right data structure. A TreeMap is sorted by key so you could simply iterate over the entries saving the first one which exceeds the current maximum.

• Janardhan Maithil: You mean something like this Map<String, Long> map = Arrays.stream(votes).collect(Collectors.groupingBy(Function.identity(), TreeMap::new, Collectors.counting())); long max = 0; String result = ""; for (Map.Entry<String, Long> e : map.entrySet()) { if (e.getValue() > max) { max = e.getValue(); result = e.getKey(); } } return result;
• Mark Bluemel: That was my thinking. I'm not in a position to try it at the moment, however. Does it work for you?

Answer 2

I think since you just need the winner, we can use the reduce operation post collecting the data in map, that will reduce the overall time complexity as well. Adding the modified version of the code here, we are just using Hashmap like you used, and then using reduce operation to find out the winner.

 private static String findWinner(String[] votes) {
return Arrays.stream(votes).collect(
 Collectors.groupingBy(Function.identity(), HashMap::new, Collectors.counting()))
 .entrySet().stream()
 .reduce((x, y) -> {
 if (x.getValue().compareTo(y.getValue()) > 0) {
 return x;
 } else if (x.getValue().compareTo(y.getValue()) < 0) {
 return y;
 } else {
 return x.getKey().compareTo(y.getKey()) > 0 ? y : x;
 }
 }).map(kvp -> kvp.getKey())
 .orElse(null);

}