Programming Geek
Rated 4.7/5 based on 1446 reviews

Evernote Coding Challenge : Problem#2

This is the second problem of Evernote Coding Challenge powered by Interview street.

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
                        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