Algorithm to print asterisks for duplicate characters [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this 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

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;
}

Answer 2

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 3

If the alphabet under consideration is fixed, it can be done in two passes:

1. Create an integer array A with the size of the alphabet, initialized with all zeros.
2. Create a boolean array B with size of the input, initialize with all false.
3. Iterate the input; increase for every character the corresponding content of A.
4. Iterate the input; output a character if its value it B is false and set its value in B to true. Finally, output a carriage return.
5. Reset B.
6. Iterate input as in 4., but print a star if if the character's count in A is positive, then decrease this count; print a space otherwise.
7. Output a carriage return; loop to 5 as long as there are any stars in the output generated.

Answer 4

This is interesting. You shouldnt use a stl::map because that is not a hashmap. An stl map is a binary tree. An unordered_map is actually a hash map. In this case we dont need either. We can use a simple array for char counts.

void printAstr(std::string str){
 int array[256] ;// assumining it is an ascii string
 memset(array, 0, sizeof(array));
 int astrCount = 0;
 for(int i = 0; i < str.length()-1; i++){
     array[(int) str[i]]++;
     if(array[(int) str[i]] > 1) astrCount++;
 }
std::cout << str  << std::endl;
for(int i = 0;  i < str.length()-1;i++) std::cout << "* ";
std::cout << std::endl;
while(astrCount != 0){
   for(int i= 0; i< str.length() - 1;i++){
       if(array[(int) str[i]] > 1){
          std::cout << "* ";
          array[(int) str[i]]--;
          astrCount--;
       }else{
        std::cout << " ";
       }
   }
   std::cout << std::endl;
}

}

pretty simple just add all values to the array, then print them out the number of times you seem them.

EDIT: sorry just made some logic changes. This works now.

Answer 5

The following code works correctly. I am assuming that you can't use std::string and take note that this doesn't take overflowing into account since I didn't use dynamic containers. This also assumes that the characters can be represented with a char.

#include <iostream>

int main()
{
    char input[100];
    unsigned int input_length = 0;
    char letters[100];
    unsigned int num_of_letters = 0;
    std::cin >> input;
    while (input[input_length] != '\0')
    {
        input_length += 1;
    }
    //This array acts like a hash map.
    unsigned int occurrences[256] = {0};
    unsigned int max_occurrences = 1;
    for (int i = 0; i < input_length; ++i)
    {
        if ((occurrences[static_cast<unsigned char>(input[i])] += 1) == 1)
        {
            std::cout<< " " << (letters[num_of_letters] = input[i]) << " ";
            num_of_letters += 1;
        }
        if (occurrences[static_cast<unsigned char>(input[i])] > max_occurrences)
        {
            max_occurrences = occurrences[static_cast<unsigned char>(input[i])];
        }
    }
    std::cout << std::endl;
    for (int row = 1; row <= max_occurrences; ++row)
    {
        for (int i = 0; i < num_of_letters; ++i)
        {

            if (occurrences[static_cast<unsigned char>(letters[i])] >= row)
            {
                std::cout << " * ";
            }
            else
            {
                std::cout << "   ";
            }

        }
        std::cout << std::endl;
    }
    return 0;
}

Answer 6

The question is marked as c++ but It seems to me that the answers not are all quite C++'ish, but could be quite difficult to achieve a good C++ code with a weird requirement like "not to use any library". In my approach I've used some cool C++11 features like in-class initialization or nullptr, here is the live demo and below the code:

struct letter_count
{
    char letter = '\0';
    int count = 0;
};

int add(letter_count *begin, letter_count *end, char letter)
{
    while (begin != end)
    {
        if (begin->letter == letter)
        {
            return ++begin->count;
        }
        else if (begin->letter == '\0')
        {
            std::cout << letter; // Print the first appearance of each char
            ++begin->letter = letter;
            return ++begin->count;
        }

        ++begin;
    }

    return 0;
}

int max (int a, int b)
{
    return a > b ? a : b;
}

letter_count *buffer = nullptr;

auto testString = "supergalifragilisticoespialidoso";

int len = 0, index = 0, greater = 0;

while (testString[index++])
    ++len;

buffer = new letter_count[len];

for (index = 0; index < len; ++index)
    greater = max(add(buffer, buffer + len, testString[index]), greater);

std::cout << '\n';

for (int count = 0; count < greater; ++count)
{
    for (index = 0; buffer[index].letter && index < len; ++index)
        std::cout << (count < buffer[index].count ? '*' : ' ');

    std::cout << '\n';
}

delete [] buffer;

Since "no libraries are allowed" (except for <iostream>?) I've avoided the use of std::pair<char, int> (which could have been the letter_count struct) and we have to code many utilities (such as max and strlen); the output of the program avobe is:

supergaliftcod
**************
* *******   * 
*     ***   * 
*       *     
        *     
        *     

Answer 7

My general solution would be to traverse the word and replace repeated characters with an unused nonsense character. A simple example is below, where I used an exclamation point (!) for the nonsense character (the input could be more robust, some character that is not easily typed, disallowing the nonsense character in the answer, error checking, etc). After traversal, the final step would be removing the nonsense character. The problem is keeping track of the asterisks while retaining the original positions they imply. For that I used a temp string to save the letters and a process string to create the final output string and the asterisks.

#include <iostream>
#include <string>

using namespace std;

int
main ()
{
  string input = "";
  string tempstring = "";
  string process = "";
  string output = "";
  bool test = false;

  cout << "Enter your word below: " << endl;
  cin >> input;

  for (unsigned int i = 0; i < input.length (); i++)
  { //for the traversed letter, traverse through subsequent letters    
    for (unsigned int z = i + 1; z < input.length (); z++)
    {
        //avoid analyzing nonsense characters
        if (input[i] != '!')    
        {           
          if (input[i] == input[z]) 
          { //matched letter; replace with nonsense character
            input[z] = '!';
            test = true;    //for string management later
          }
        }
    }
    if (test)   
    {
      tempstring += input[i];
      input[i] = '*';
      test = false; //reset bool for subsequent loops
    }
  }

  //remove garbage symbols and save to a processing string
  for (unsigned int i = 0; i < input.size (); i++)
    if (input[i] != '!')
      process += input[i];

  //create the modified output string
  unsigned int temp = 0;
  for (unsigned int i = 0; i < process.size (); i++)
    if (process[i] == '*')
    { //replace asterisks with letters stored in tempstring
      output += tempstring[temp];
      temp++;
    }
    else
      output += process[i];

   //output word with no repeated letters
  cout << output << endl;

  //output asterisks equal to output.length
  for (unsigned int a = 0; a < output.length (); a++)
    cout << "*";

  cout << endl;

  //output asterisks for the letter instances removed
  for (unsigned int i = 0; i < process.size (); i++)      
    if (process[i] != '*')
      process[i] = ' ';

  cout << process << endl << endl;
}

Sample output I received by running the code:

Enter your word below: 
INDIA
INDA
****
*

Enter your word below: 
abcdefgabchijklmnop
abcdefghijklmnop
****************
***

Answer 8

It is possible just using simple array to keep count of values.

#include<iostream>
#include<string>

using namespace std;

int main(){

    string s;
    char arr[10000];
    cin>>s;
    int count1[256]={0},count2[256]={0};
    for(int i=0;i<s.size();++i){
        count1[s[i]]++;
        count2[s[i]]++;
    }
    long max=-1;
    int j=0;
    for(int i=0;i<s.size();++i){
        if(count1[s[i]]==count2[s[i]]){ //check if not printing duplicate
            cout<<s[i]; 
            arr[j++]=s[i];
        }
        if(count2[s[i]]>max)
            max=count2[s[i]];
        --count1[s[i]];
    }
    cout<<endl;
    for(int i =1; i<=max;++i){
        for(int k=0;k<j;++k){
            if(count2[arr[k]]){
                cout<<"*";
                count2[arr[k]]--;
            }
            else
                cout<<" ";
        }
        cout<<endl;

    }

}