CareerCup

import java.util.*;
public class hash {

public static void main(String[] args) {


String str[] = {"russia","japan","russia","india"};
int len = 4;
Hashtable ht = new Hashtable();
int i=0;
while(i<len)
{

String c = str[i];
System.out.println("c :"+c);
Integer intg = (Integer) ht.get(c);

if(intg ==null)
ht.put(c,new Integer(1));
else
ht.put(c,new Integer(intg.intValue()+1));

i++;
}

Enumeration k = ht.keys();

while(k.hasMoreElements()){
String key = (String) k.nextElement();
System.out.println( key + " > "+ ht.get(key) );
}
}

}

After inserting all of them in the hashMap we can make tree sets of the same value types.

Correct algorithm is TRIE tree

Most efficient doesn't mean anything. Most efficient in space, time, what?

This solution takes too much memory but the average time complexity is O(n log n)

Have a hash table with words as the key and its frequency as the value. Then have a binary search on the frequency of words, each node in the binary search tree will have two values one is the frequency of words on which the binary search tree is built and the other is reference to another binary search tree which contains the words for this frequency.

When ever we encounter insert a word into the hash table insert it in the binary search tree also and whenever a word s frequency is altered in the hash table , lets say a word 'japan' frequency is increased from 2 to 3 , then delete japan from the 'word binary search tree' which referenced by the 'frequency binary search tree' node which has the value of 2 and insert into the 'word binary search tree' referenced by the 'frequency binary search tree' node which has got the value 3 in it.
To display the the output in the desired format do post-order traversal of the 'frequency binary search tree' and in-order traversal of the corresponding 'word binary search tree' pointed each node of the 'frequency binary search tree'

#include<iostream>
#include<fstream>
#include<map>
#include<vector>
using namespace std;

int main()
{
	fstream my;
	my.open("input.txt", fstream::in);
	map<string, int> mymap;
	map<int, vector<string> > outmap;
	map<string, int>::iterator it;
	string s;
	while( !my.eof() )
	{
		s.clear();
		my >> s;
		if( s.empty() )
			continue;
		it = mymap.find(s);
		if( it == mymap.end())
			mymap[s] = 1;
		else
			it->second++;
			
	}
	vector<string> temp;
	map<int, vector<string> >::iterator mit;
	for( it = mymap.begin(); it != mymap.end(); it++){
		temp.clear();
		temp.push_back(it->first);
		
		mit = outmap.find( it->second );
		if( mit == outmap.end())
			outmap[it->second] = temp;
		else
			outmap[it->second].push_back(it->first);
	}
	map<int, vector<string> >::reverse_iterator rit;
	vector<string>::iterator vit;
	for( rit = outmap.rbegin(); rit != outmap.rend(); rit++ )
		for( vit = rit->second.begin(); vit != rit->second.end(); vit++)
			cout << "\n" << *vit << " : " << rit->first;


	cout << endl;
	return 0;
}

input.txt contains

austin
japan
usa
japan
russia
usa
japan
japan
australia

public class algo {

static class node implements Comparable<node>{
String data;
Integer count;
public node(String data,Integer count){
this.data = data;
this.count =count;

}

public int compareTo(node obj){
if(this.count==obj.count)
return this.data.compareTo(obj.data);//in ascending order of name
else
return obj.count.compareTo(this.count);// in decending order of count

}

public String toString(){
return this.data+":"+this.count;
}

}

public static void main(String[] args) {

String str[] = new String[] { "japan", "usa", "japan",
"russia", "usa", "japan", "japan", "australia" };

HashMap<String, Integer> hm = new HashMap<String, Integer>();

for(String s:str){
hm.put(s,hm.get(s)==null?1:hm.get(s)+1);
}

Iterator<String> itr = hm.keySet().iterator();
Set<node> s = new TreeSet<node>();

while(itr.hasNext()){
String key = itr.next();
s.add(new node(key,hm.get(key)));
}

System.out.println(s);
}
}

create an array of frequencies as well as string names from the input text.
not sort the array based on the following comparator

bool operator < (const void *a, const void *b ) {
int x;
if (a->frequency < b->frequency)
return 1;
if (a->frequency > b->frequency)
return -1;
if (a->frequency == b->frequency) {
x = strcmp(a->name, b->name);
if (x<0) 
return 1;
if (x>0)
return -1;
if (x==0)
return 1;
}

hash table and max heap.
In hash table the key will be word and value will the address of the node in max heap(which has the count).if the word exist increase the count in heap and heapify .after reading the whole file delete root and heapfify( n times).heap should also has the index of word in hash table.to print the word at the end.