CareerCup

Put all the words in a trie and update its frequency when the same word is detected. And atlast print all the words present in that trie.

Maintaining a hash table that stores frequency of occurrence of the alphabet would provide 2 things.. 1. Help to implement delete duplicate logic 2. Provide frquency

Using same hash table..now those entries of the hash table that have non-zero frequency would be printed and they will be automatically in alphabetical order.
Hash table size = 22.. no. of characters a-z... you might wanna convert every alphabet
to a lower case value for use with below mentioned hash function..
Hashing function is h(k) = ASCII of k

@CodeGeek
Thanks for posting a solution, although I believe the question is for strings, i.e combination of alphabets. I think the solution u have posted is for sorting alphabets not strings.

if it is for strings can you elaborate on the hashfunction -> h(k) = ASCII of k, considering k is a string, can you explain what does ASCII of k means in greater detail.

Although I agree that putting them in a hashtable will take care of duplicates and frequency, although how they get sorted automatically is not clear.

Create a binary tree of strings. Each node has an additional filed (number of occurence of the sreing, default value is 1). whenever while inserting a new string(node) to the tree, if the string already exists, then just increment the count.
Its time complexity is O(n). Once all the strings are added, do a traversal of the tree. its time complexity will be O(log n). so total time = O(n) + O(lg n) which is O(n)

we can create an heap and insert the elements in it,
the node in heap is also having one extra field called the count,
so if any item come again which is already in the tree,
we just need to increase the count.
than we can sort then using heap sort.

time complexity: O(nlgn)
space complexity: O(n) + space for pointers.

its more like maintaining a weight balanced tree but not rebalancing it as it is required to do so in weight balanced tree.
pseudo code would be:

typedef struct node
{
char* str;
int freq;
struct node *left,*right;
}mynode;
typedef mynode* nodeptr;
insert(char*str,nodeptr *tree)
{
nodeptr p=*tree;
nodeptr backp = Null;
int i;
//1.search if already in tree
while(p!=Null)
{
if((i=strcmp(str,p))==0)//found
{
p->freq+=1;
return p;
}
else //not this node
{
if(i<0)
{
backp = p;
p=p->left;
}
else
{
backp = p;
p=p->right;
}
}
}
//if not found add a new node
nodeptr q = newnode(str);
q->left=q->right=null;
q->freq=0;
if(strcmp(backp->str,str)>0)
backp->left = q;
else
backp->right = q;
}

//the string needs to be tokenized first
int main()
{
char *lstr = "This is a long string";
char *p;
p=strtok(lstr," ");
if(p!=null)
{
do
{
p=strtok(null," ");
if(p==null)
break;
else
insert(p);
}while(1);
}
}

I thin hash table would be the fastest one and hash function will be sum of the characters making the string
Am i right??

in my view 1 solution can be-
1. using hash table with hash function using 26 prime method store the strings and sort the table based on frequency which will be stored with string
2. using tries/suffix trees with frequency count in each node but that would need sorting later on

void prog(char *str){
int a[26]; /*we are assuming string is having characters from a-z,same can be extended to other chars*/
int len = strlen(str);
while(*str){
a[*str++ - 'a']+=1;
}

for(i=0;i<26;i++){
if(a[i]){
printf("char=%c freq=%d",a[i]+'a',a[i]);
*str++=a[i]+'a';
}
}
*str='\0';
printf("\n%s",str);
}

nice algo...

{{Java code :

public void readers(){
Map <String,Integer>s=new TreeMap<String,Integer>();
String str="hi hi hi fdshkjf fskjh fshk fs hfaa ha aa aaa aa a b";
String strArr[]=str.split(" ");
for(int i=0;i<strArr.length;i++){
int count=0;
if(s.get(strArr[i])!=null){
count=s.get(strArr[i]);
}

s.put(strArr[i],++count);

}



System.out.println(s.tostring());

}



OtherAlgo:

1. Sort the string using any sorting algorithm.
2. now traverse and add count between by deleting dups

}}