Most frequent word in an array of strings? OR Find winner of an election where votes are represented as candidate names?
Question: Most frequent word in an array of strings? OR Find winner of an election where votes are represented as candidate names? Solution: Given an array of names of candidates in an election. A candidate name in array represents a vote casted to the candidate. Print the name of candidates received Max vote. If there is tie, print lexicographically smaller name. OR Given an array of words find the most occurring word in it. Input : arr[] = {"Abhinaw", "for", "Abhinaw", "Abhinaw", "portal", "to", "learn", "can", "be", "computer", "science", "zoom", "yup", "fire", "in", "be", "data"} Output : Abhinaw "Abhinaw" is the most frequent word as it. occurs 3 times So i can think of like this: 1) Run two loops and count occurrences of every word. Time complexity of this solution is O(n * n * MAX_WORD_LEN). But i have an another efficient solution also which is below: 2)Trie data structure: The idea is simple first we will insert in trie. In trie, we keep counts of words ending at a node. We do preorder traversal and compare count present at each node and find the maximum occurring word. Time Complexity : O(n * MAX_WORD_LEN) 3)Hashing: I have Hashing solution also and which is more efficient solution than above.Have a look into the code. Sample Code: import java.util.HashMap; import java.util.Map; /** * */ /** * @author Abhinaw.Tripathi * */ public class MostFrequentWordOrElectricVotingApp { public static void main(String[] args) { String[] votes = { "Abhinaw", "Gaurav", "Abhishek", "Garima", "babli", "Logesh", "Lalitha", "Pawan", "Abhinaw", "Abhinaw", "Garima", "Abhinaw", "Abhinaw" }; findWinner(votes); } public static void findWinner(String votes[]) { Map<String,Integer> map =new HashMap<String, Integer>(); for (String str : votes) { if (map.keySet().contains(str)) map.put(str, map.get(str) + 1); else map.put(str, 1); } int maxValueInMap = 0; String winner = ""; for ( Map.Entry<String,Integer> entry : map.entrySet()) { String key = entry.getKey(); Integer val = entry.getValue(); if (val > maxValueInMap) { maxValueInMap = val; winner = key; } // If there is a tie, pick the else if (val == maxValueInMap && winner.compareTo(key) > 0) winner = key; } System.out.println("Winning Candidate is :" +winner); } } Output: Winning Candidate is :Abhinaw