CareerCup

1. Create a hash from the string
2. Sort the hash
3. Return the character from the entry num-1 in this sorted array

Time complexity: O(m) + O(nlog(n)) where m is size of string and n is size of hash table/array
Space: O(n) where n is size of hash array

The implementation is Java specific but can be done in other languages

Instead of using char[] as hashMap we can use an array of HashElem[] as the hash where HashElem is

public class HashElem {
		public char elem;
		public int count;

		public HashElem(char c, int count) {
			this.elem = c;
			this.count = count;
		}
	}

Now we can initialize this hash using the characters of the original string as index. Next step is to sort this hash (which is actually an array) based on the count or individual characters and if counts are same based on the character ascii value. I have overridden the standard comparator interface. Here is a sample code to get you started:

import java.util.Arrays;
import java.util.Comparator;

public class MostCommonChar {

	public class HashElem {
		public char elem;
		public int count;

		public HashElem(char c, int count) {
			this.elem = c;
			this.count = count;
		}
	}

	public class MyComparator implements Comparator<HashElem> {

		@Override
		public int compare(HashElem o1, HashElem o2) {
			int result = 0;

			if (o1 == null && o2 == null) {
				result = 0;
			} else if (o1 == null) {
				result = 1;
			} else if (o2 == null) {
				result = -1;
			} else if (o1.count != o2.count) {
				result = o2.count - o1.count;
			} else if (o1.elem != o2.elem) {
				result = o2.elem - o1.elem;
			}
			return result;
		}
	}

	private HashElem[] h = new HashElem[256];
	
	public char findMostCommonChar(String str, int k) {

		if (k <= 0 || k > str.length()) {
			return 0;
		}

		
		int i;
		char index;

		for (i = 0; i < 255; i++) {
			h[i] = null;
		}

		for (i = 0; i < str.length(); i++) {
			index = str.charAt(i);
			if (h[index] == null) {
				h[index] = new HashElem(index, 1);
			} else {
				h[index].count++;
			}
		}

		Arrays.sort(h, new MyComparator());

		return h[k - 1] == null ? 0 : h[k - 1].elem;
	}

	public static void main(String[] args) {

		String s = "aabra ka daabra";
		MostCommonChar m = new MostCommonChar();
		System.out.println(m.findMostCommonChar(s, 1));
		System.out.println(m.findMostCommonChar(s, 2));
		System.out.println(m.findMostCommonChar(s, 3));
		System.out.println(m.findMostCommonChar(s, 4));
		System.out.println(m.findMostCommonChar(s, 5));
		System.out.println(m.findMostCommonChar(s, 6));
		

	}

}

// output: a r b <space> k d

Take a 256 integer array. Now once a charater is scanned increase the frequency of the character in the integer array according to its ASCII value

Do we need to maintain 256 length array. if we know the string consists only of letters we can maintain an array of 26 and use counting sort.

Python code:

char MostCommonChar(String str, int num):
char_count = char_count(string) # returns each char to its count dictionary
chars_dict = sorted(char_count.values())
char_dict = chars_dict[num-1]
print char_dict[0]


#Hasing key is char and value is count
def char_count_dict(string):
char_count = {} #Map each char to its count
for char in string
if char in char_count:
char_count[char] = char_count[char] + 1
else:
char_count[char] = 1
return char_count

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package amazon;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
*
* @author ashok
*/
public class MostCommonChar {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
MostCommonChar main = new MostCommonChar();
System.out.print("character is " + main.mostCommonChar("Aabra ka dabra", 1));
}

private char mostCommonChar(String str, int num) {
char commonChar = 'a';
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
if (map.containsKey(str.charAt(i))) {
int n = map.get(str.charAt(i));
map.put(str.charAt(i), n + 1);
} else {
map.put(str.charAt(i), 1);
}
}
List<OccuranceClass> oc = new ArrayList<OccuranceClass>();
for (Object obj : map.keySet().toArray()) {
//ystem.out.println(obj + " " + map.get(obj));
oc.add(new OccuranceClass((Character) obj, (Integer) map.get(obj)));
}
Collections.sort(oc, new Sort());
return oc.get(num - 1).getCh();
}

static private final class Sort implements Comparator<OccuranceClass> {

public int compare(OccuranceClass o1, OccuranceClass o2) {
return o2.getI() - o1.getI();
}
}

static private final class OccuranceClass {

public OccuranceClass(char ch, int i) {
this.ch = ch;
this.i = i;
}
private char ch;
private int i;

public char getCh() {
return ch;
}

public void setCh(char ch) {
this.ch = ch;
}

public int getI() {
return i;
}

public void setI(int i) {
this.i = i;
}
}
}

import java.util.HashMap;

public class MostCommonChar {
	private static class CharCount {
		public char character;
		public int count;
		
		CharCount(Character ch, Integer count) {
			this.character = ch;
			this.count = count;
		}
	}

	public static char mostCommonChar(String str, int num) {
		char output = ' ';
		HashMap<Character, Integer> charOccuranceHashMap = new HashMap<Character, Integer>();
		for(int index = 0; index < str.length(); index++) {
			char ch = str.charAt(index);
			if(charOccuranceHashMap.containsKey(ch)) 
				charOccuranceHashMap.put(ch, charOccuranceHashMap.get(ch) + 1);
			else
				charOccuranceHashMap.put(ch, 1);
		}
		
		//Converting the HashMap to a Array
		CharCount[] sortedCharCount = new CharCount[charOccuranceHashMap.size()];
		int index = 0;
		for(char key : charOccuranceHashMap.keySet())
			sortedCharCount[index++] = new CharCount(key, charOccuranceHashMap.get(key));		
		
		//Occurrence sort
		for(int outerIndex = 0 ; outerIndex < sortedCharCount.length; outerIndex++) {
			for(int innerIndex = 0; innerIndex < outerIndex; innerIndex++) {
				if(sortedCharCount[innerIndex].count < sortedCharCount[outerIndex].count) {
					//swap the positions
					CharCount temp = sortedCharCount[innerIndex];
					sortedCharCount[innerIndex] = sortedCharCount[outerIndex];
					sortedCharCount[outerIndex] = temp;
				}
			}
		}
		
		if(num <= sortedCharCount.length) 
			output = sortedCharCount[num - 1].character;
		
		return output;
	}
}

public class Main {
	public static void main(String args[]) {
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 1));
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 2));
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 3));
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 4));
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 5));
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 6));
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 7));
		System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 8));
	}	
	
}

def getnthmostrep(in_str, n):
str_dict = {}
for echar in in_str:
if echar not in str_dict:
str_dict[echar]=1
else:
str_dict[echar]+=1
print str_dict.items()[n-1][0]

package com.DataStr.Question;
import java.util.*;


public class Question1 {

Set<Character> charSet = new HashSet<Character>();
Map<Character,Integer> charMap = new HashMap<Character, Integer>();
Map<Integer, String> sortedMap = new TreeMap<Integer, String>();

public String mostCommonChar(String str, int num){
for(int i = 0; i < str.length(); i++)
charSet.add(str.charAt(i));
for(int i = 0; i < str.length(); i++)
charMap.put(str.charAt(i), 0);
for(int i = 0; i < str.length(); i++)
charMap.put(str.charAt(i), charMap.get(str.charAt(i))+1);

Object []key = charMap.keySet().toArray();
Object []values = charMap.values().toArray();

for(int i = 0; i < values.length; i++){
sortedMap.put(Integer.parseInt((values[i].toString())), (sortedMap.get(values[i]) == null) ? key[i].toString() : sortedMap.get(values[i]) + key[i].toString() );
}

key = sortedMap.keySet().toArray();
if(num <= sortedMap.size())
return sortedMap.get(Integer.parseInt(key[key.length - num].toString()));
else
return "";
}



public static void main(String[] args) {
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 1));
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 2));
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 3));
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 4));
}

}

Take a 256 integer array. Initialize each of its value to zero. Increment its value according to the character. Now convert this array as a max heap. Get the count of character according to 'num' by removing max element and reduce the length of the heap by 1. Finally get the required count.
Eg: If need third largest, initially we have to remove top element from the heap two times and take third highest element as answer.

maintain an 256 integer array and by using heap to get the specific number of node.

Maintain a dictionary with key as the character, the value would be an object of a class with properties like character, count and a position in the list. The list consist of objects to the class defined above i.e. a reference to the object exists in both the list and the dictionary.

Now traverse the string and create these objects. Keep the list sorted according to the new count and update necessary entries in dictionary as well as the list.

Maintain a dictionary with key as the character, the value would be an object of a class with properties like character, count and a position in the list. The list consist of objects to the class defined above i.e. a reference to the object exists in both the list and the dictionary.

Now traverse the string and create these objects. Keep the list sorted according to the new count and update necessary entries in dictionary as well as the list.