Algorithm to print asterisks for duplicate characters [closed]

Question

I was asked this question in an interview:
Given an array with the input string, display the output as shown below

Input

INDIA  

Output

INDA  
****  
* 

I iterated through the array and stored each character as a key in std::map with value as number of occurrence. Later I iterate the map and print the asteriks and reduce the value in the map for each character.

Initially, I was asked not to use any library. I gave a solution which needed lot of iterations. For every character, iterate the complete array till the index to find previous occurrences and so on. Is there any better way, e.g. better complexity, such as faster operation, by which this can be achieved?

Answer 1

Essentially what you are asking is how to implement map without using the STL code, as using some kind of data structure which replicates the basic functionality of map is pretty much the most reasonable way of solving this problem.

There are a number of ways of doing this. If your keys (here the possible characters) come from a very large set where most elements of the set don't appear (such as the full Unicode character set), you would probably want to use either a tree or a hash table. Both of these data structures are very important with lots of variations and different ways of implementing them. There is lots of information and example code about the two structures around.

As @PeterG said in a comment, if the only characters you are going to see are from a set of 256 8-bit chars (eg ASCII or similar), or some other limited collection like the upper-case alphabet you should just use an array of 256 ints and store a count for each char in that.

Answer 2

here is another one: You can see it working HERE

#include <stdio.h>
int main()
{
    int i,j=0,f=1;
    char input[50]={'I','N','D','I','A','N','A','N'};
    char letters[256]={0};
    int counter[256]={0};
    for(i=0;i<50;i++)
    {
        if(input[i])
         counter[input[i]]++;
         if(counter[input[i]]==1)
         {
            putchar(input[i]);
            letters[j]=input[i];
            j++;
         }    
    }
    putchar('\n');
    while(f)
    {
        f=0;      
        for(i=0;i<j;i++)
            if(counter[letters[i]])
            {
                putchar('*');
                counter[letters[i]]--;
                f=1;
            }
            else
            {
                putchar(' ');
            }
        putchar('\n');  
    }
    return 0;
}