This is the second problem of Evernote Coding Challenge powered by Interview street.
Step 4: create a list from hash map and sort the list based on values.
Step 5: Display k most frequent terms in descending order of the frequency as the list is now sorted.
Frequency Counting of Words / Top N words in a document.
Given N terms, your task is to find the k most frequent terms from given N terms.
Input format
First line of input contains N, denoting the number of terms to add.
In each of the next N lines, each contains a term.
Next line contains k, most frequent terms.
Output format
Print the k most frequent terms in descending order of their frequency. If two terms have same frequency print them in lexicographical order.
Sample input
14
Fee
Fi
Fo
Fum
Fee
Fo
Fee
Fee
Fo
Fi
Fi
Fo
Fum
Fee
3
Sample output
Fee
Fo
Fi
Constraint
0 < N < 300000
0 < term length < 25.
Algorithm :
Step 1: read n
Step 2: for i=0 to n do step3
Step 3: if ith term is already in hash map then
Step 1: read n
Step 2: for i=0 to n do step3
Step 3: if ith term is already in hash map then
increment the value of value by 1.
else
put an entry in hash map, key as ith term and value as 1.
Step 4: create a list from hash map and sort the list based on values.
Step 5: Display k most frequent terms in descending order of the frequency as the list is now sorted.
Here goes the program for the same :
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.Map; import java.util.Scanner; import java.util.TreeMap; /** * * @author VIK */ public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine().trim()); int k = 0; TreeMap<String, Integer> tm = new TreeMap<String, Integer>(); for (int i = 0; i < n; i++) { String s = sc.nextLine(); if (tm.containsKey(s)) { tm.put(s, tm.get(s) + 1); } else { tm.put(s, 1); } } k = Integer.parseInt(sc.nextLine().trim()); ArrayList ls = new ArrayList(tm.entrySet()); Collections.sort(ls, new Compare()); Iterator iterator = ls.iterator(); while (iterator.hasNext() && k > 0) { Map.Entry e = (Map.Entry) iterator.next(); if (k != 1) { System.out.println(e.getKey()); } else { System.out.print(e.getKey()); } k--; } } static class Compare implements Comparator { @Override public int compare(Object o1, Object o2) { int result = 0; Map.Entry e1 = (Map.Entry) o1; Map.Entry e2 = (Map.Entry) o2; int val1 = (Integer) e1.getValue(); int val2 = (Integer) e2.getValue(); if(val1==val2) return ((String)e1.getKey()).compareToIgnoreCase((String)e2.getKey()); return val2 - val1; } } }
No comments :
Post a Comment