Given an input string, print out the N most common characters in that string.

Question

Anonymous · Accepted Answer

import java.util.*;

public class freq {

    public static void frequency(String str, int N)
    {
    	
        Map sortedFreqCount = new TreeMap();
        for(int i = 0; i  entry : sortedFreqCount.entrySet())
        {
        	if(printCount == N) break;
        	Character key = entry.getKey();
        	Integer value = entry.getValue();
        	System.out.println(printCount + ".) " + key + " -> " + value);
        	printCount++;
        }
    }
    
    public static > Map sortByValues(final Map map)
    {
    	Comparator valueComparator =  new Comparator() {
    	    public int compare(K k1, K k2) {
    	        int compare = map.get(k2).compareTo(map.get(k1));
    	        if (compare == 0) return 1;
    	        else return compare;
    	    }
    	};
    	Map sortedByValues = new TreeMap(valueComparator);
    	sortedByValues.putAll(map);
    	return sortedByValues;
    }
    
    public static void main(String[] args)
    {
        String test = "aaaaaaaaaaaaaaaaaaakkkkkkkkkkkkkkkkkkkddddddddddddhhhhhhhhhbbbbbbbeeeewqqqer";
        frequency(test,10);
    }

}

Marco · Answer

Iterate through the string and save each character inside and hashmap, if the character exists already in the map just increase its number of occurrences. once you're done with registering the occurrences of each char, iterate through the map and while iterating create a linked list ordered in decreasing order. Than take the first N elements of the list. The time total time complexity is O(n) with n being the length of the string. This is because all the other operations have a constant time, since you cannot have more than 256 different chars, independently from the lenght of the string.

Palantir Technologies

Palantir Technologies Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches