CareerCup

Create a max heap taking freq as the comparison point
Now the first 5 elements will be the 5 most common
Time complexity O(nlogn)

Why can't we use weight balanced trees?

We can use Counting Sort to count the occurrence of a particular alphabets which will requires an auxillary array and operation will be done and O(n)time. And then iterate through this auxillary array to get the max occurrence and corresponding alphabet.

I would recommend using suffix trees.

#include<iostream.h>
#include<conio.h>
#include<string.h>
void main()
{
clrscr();
char a1[]={'a','b','c','b','c','d','d','b'};
int b[128];
for(int k=0;k<128;k++)
b[k]=0;
for(int i=0;i<strlen(a1);i++)
b[(int)a1[i]]++;
for(i=0;i<128;i++)
{
if(b[i]>0)
cout<<"\n"<<(char)i<<" repeats\t"<<b[i]<<"times";
}
getch();
}

can be easily done by taking a
map<string,int> table;

then scan the string and do table[str]++;
in the end print the last 5 values;

map<string, int>::iterator it;
it=table.end();
for(i=0;i<5;i++)
{
cout<<(*it).first;
if(it!=table.begin())it--; else exit;
}

use a hashmap and keep the chars as keys ... increment the value as and when u get characters .. this wld run in O(n) time , and will take O(2^32) space maximum (Considering that all unicode characters are considered)

Guys..Why don't you use treemap rather than Hashmap. TreeMap can sort the data automatically using the comparable or comparator interface.

I think using java classes like treemap or hashmap would not be accepted.
Anyways i too had thought of a hash table sort of structure.
We can design our own hashtable class but ultimately need to have a way to sort the hashtable. In that case it will take O(n) for scanning the elements and putting their counts in hashtable+ O(mlogm) for sorting the hashtable elements. I may b wrng but mlogm could be taken as constant as it depends on number of possible elements as keys

I think using java classes like treemap or hashmap would not be accepted.
Anyways i too had thought of a hash table sort of structure.
We can design our own hashtable class but ultimately need to have a way to sort the hashtable. In that case it will take O(n) for scanning the elements and putting their counts in hashtable+ O(mlogm) for sorting the hashtable elements. I may b wrng but mlogm could be taken as constant as it depends on number of possible elements as keys

I think using java classes like treemap or hashmap would not be accepted.
Anyways i too had thought of a hash table sort of structure.
We can design our own hashtable class but ultimately need to have a way to sort the hashtable. In that case it will take O(n) for scanning the elements and putting their counts in hashtable+ O(mlogm) for sorting the hashtable elements. I may b wrng but mlogm could be taken as constant as it depends on number of possible elements as keys

I think using java classes like treemap or hashmap would not be accepted.
Anyways i too had thought of a hash table sort of structure.
We can design our own hashtable class but ultimately need to have a way to sort the hashtable. In that case it will take O(n) for scanning the elements and putting their counts in hashtable+ O(mlogm) for sorting the hashtable elements. I may b wrng but mlogm could be taken as constant as it depends on number of possible elements as keys

I would create two data structures. 1 Hash map, 1 hashset. The hashmap will have key as character and value as count. hashset will work as a placeholder for the items that are already added to hashmap. So
if (!hashset.add("a")) {
i=hashmap.get("a");
i++;hashmap.put("a",i)
}
else
hashmap.put("a",i)

Iterate thru the whole array and calculate the frequency.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class CommonOccuring {

public static void main(String[] args) {
String[] arr = { "a", "b", "c", "f", "a", "d", "e", "f", "b", "f", "f" };
Map<String, Integer> map = new HashMap<String, Integer>();
int count = 1;
map.put(arr[0], count);
for (int i = 1; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
map.put(arr[i], map.get(arr[i])+1);
}else{
map.put(arr[i], 1);
}
}
Iterator<Map.Entry<String, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<String, Integer> entry = entries.next();
System.out.println( entry.getKey() + " " + entry.getValue());
}

}

}

public Hashtable countAlphabet (String astring) {

Hashtable table = new Hashtable(); If (astring.length> 4000) return table;

StringBuffer buffer = new StringBuffer(aString);

while (buffer.length() > 0){ String firstChar = buffer.substring(0, 1);

Integer count (Integer) table.get(firstChar);

if (count == null){ count = new Integer (1);

}else{

}

Count = new Integer (count. intvalue() + 1);

table.put(firstChar, count); buffer.delete(0, 1);

} return table;

public Hashtable countAlphabet (String astring) {

Hashtable table = new Hashtable(); If (astring.length> 4000) return table;

StringBuffer buffer = new StringBuffer(aString);

while (buffer.length() > 0){ String firstChar = buffer.substring(0, 1);

Integer count (Integer) table.get(firstChar);

if (count == null){ count = new Integer (1);

}else{

}

Count = new Integer (count. intvalue() + 1);

table.put(firstChar, count); buffer.delete(0, 1);

} return table;