Pls help :Find first non-repeated char in a string

[varsha_saxena]

Hi Pls help me to write first non-repeated char in string . eg. If string is abcda then first non-repeated char is b . I want an efficient algo / program which will traverse the string only n times . I don't want to use hash which set bit if it encounters char .

[WaltP]

Do you want us to give you an algorithm or help you fix one you've already got? If give, read this. If fix, we're not psychic. Whatcha got?

[varsha_saxena]

Hi, I am sorry if I have violated any rules of this forum. I was interviewed and they asked me this question . I was able to provide the below Algo .But he wanted me to give a solution without using 2 - dimensional arrays.I was unable to provide a solution

2 dimensional array which will store all characters we encountered in string one by one and also number of times those char occurred in the string
For each char in original string , if no value stored in second 2 dim array then store 1.
after scanning the string array , scan the 2 dim array and return if count is 1.

Array 1 : teeth
Array 2  : t 2
e 2
h  1


return h


char FirstNonRepeated(String str)
{
Int length = strlen(str)
Char hashString[length][2];


hashString[0]=str[0];


For(i=1;i<length;i++)
{
idxrow=0;
While(idxrow!=length  )
{
If(str == hashString[idxrow][0]
{
hashString[idxrow][1] = hashString[idxrow][1] +1 ;
Exit;
}
Else
{
idxrow++;
If(idxrow ==length) //reached end but char not found
{
hashString[secondoccurence][1]=1; //first
occurrence of element
return str;
}
}//end of else


}//end of while
}//end of for


}//end of func

[Narue]

I hope that your code isn't supposed to be valid C, because it's not.

>But he wanted me to give a solution without using 2 - dimensional arrays.
Well, you can do it with a frequency table, which is essentially a one dimensional array:

char FirstNonRepeated ( const char *str )
{
  // unsigned char for space efficiency
  unsigned char saved[CHAR_MAX + 1] = {0};
  size_t i;

  // Build the frequency table
  for ( i = 0; str[i] != '\0'; i++ )
    ++saved[str[i]];

  // Return the first character with no repeats
  for ( i = 0; str[i] != '\0'; i++ ) {
    if ( saved[str[i]] < 2 )
      return str[i];
  }

  return '\0'; // No non-repeated chars
}

In C++ I would expect to see you use a map or hashmap, and if you used an array I would ask you to defend your decision. If you used a map or hashmap I would ask you to defend your decision too, so don't read into that. In an interview we try to get a good feel for how your brain works. ;)

You can also solve the problem in a less elegant manner using nested loops:

char FirstNonRepeated ( const char *str )
{
  size_t i;

  for ( i = 0; str[i] != '\0'; i++ ) {
    // Find any repeats
    int is_repeated = 0;
    size_t j;

    for ( j = 0; str[j] != '\0'; j++ ) {
      // Make sure the character skips itself
      if ( i != j && str[j] == str[i] ) {
        is_repeated = 1;
        break;
      }
    }

    if ( !is_repeated )
      return str[i];
  }

  return '\0'; // Non-repreated chars
}

Those are the two solutions I would expect to see from an interview candidate, with the former coming from someone applying for a senior position and the latter from someone applying for a junior position with no experience.

Because the question is meant to show your foundation logic, I would probably consider the nested loop function to be a failing solution most of the time even though it works. Likewise with anything more cryptic than necessary. The former suggests a weak programmer and the latter suggests a programmer with a habit of over-engineering things. A weak programmer still might make the cut if the job has some wiggle room for mentoring or if the candidate is open to alternatives.

[Aia]

@Narue

I'm a little lost with this statement in the first for loop :

++saved[str[i]];

What exactly is this line doing?.
First increment saved to what?
Second saved[whatever is pointer[index] ?]

Could you explaning it for me, please?.

Also I have a question with this line:

unsigned char saved[CHAR_MAX] = {0};

How big should I define CHAR_MAX?.

Thank you!

[Narue]

>What exactly is this line doing?
It's using a character in the string as an index into the saved array and incrementing the value stored there. The values start at zero, so you're basically counting how many of each character is stored in the string. Let's say for the sake of brevity that a char can only hold the numbers 0 through 5 and the string contains "1515325". The saved array starts out like this:

[0][0][0][0][0][0]

Going into the loop, we use each number in the string as an index into the saved array. After the loop is done, the saved array looks like this:

[0][2][1][1][0][3]

saved[1] is 2 because the string has two 1's, saved[5] is 3 because there are that many 5's in the string, and saved[2] and saved[3] are both 1 for the same reason. That's a frequency table. The value you want a frequency of is used as an index and the value stored in the table represents how many times it occurs.

The problem with a frequency table like this is that the table has to be as big as all of the possible values. For small ranges like the latin alphabet or even the ASCII character set, that's okay. An array of 256 values isn't a big hit, but if you have millions or billions of values in the range, it becomes more of an issue for storage.

>How big should I define CHAR_MAX?
CHAR_MAX is a standard macro defined in limits.h. It tells you the largest value that fits in a char.

[varsha_saxena]

Thanks a lot . I appreciate your efforts .