CareerCup

Establish a hash. The complexity is O(n).
Int findFirstNonrepeatedChar(char* str)
{
If(str == NULL) return -1;
Int hash[MAX_CHAR];
Int I;
For(i=0; str[i]!=’\0’;i++)
{
    Hash[str[i]]++;
}
For(i=0;str[i]!=’\0’;i++)
{
    If(hash[str[i]] == 1)
    {
        Return str[i];
    }
}
            }

can u explain a little?
a number in array of char ?

Find the first unique char in the given array of char. e.g. abccdee. Ans c not e

first non-reapeated character in a char array.
e.g. eabeccdebfa
Ans : d

If you can use hash_set, insert each char as you enumerate through the array and erase it as it appears more than once(if it exists in the hash_set). After one iteration the 1st in hash_set is your answer. If you can't use hash_set brute force takes O(n^2)

Here is a simpler solution

void firstunique(char *arr, int size)
{
for (int i = 0;i<size;i++)
{
if(charscount(arr,size,arr[i])==1)
cout<<"\nFirst unique char is :"<<arr[i]<<endl;
}
}

int charscount(char *arr, int size, char tofind)
{
int count=0;
for(int m = 0; m<size; m++)
{
if (arr[m] == tofind)
count++;
}
return count;
}

<pre lang="c++" line="1" title="CodeMonkey72808" class="run-this">void firstunique(char *arr, int size)
{
for (int i = 0;i<size;i++)
{
if(charscount(arr,size,arr[i])==1)
cout<<"\nFirst unique char is :"<<arr[i]<<endl;
}
}

int charscount(char *arr, int size, char tofind)
{
int count=0;
for(int m = 0; m<size; m++)
{
if (arr[m] == tofind)
count++;
}
return count;
}</pre><pre title="CodeMonkey72808" input="yes">char str_temp[] = "abcdefabcdegf";

firstunique(str_temp, sizeof(str_temp)-1);
</pre>

My answer is to use Hashmap with Char as key and int as value. Linkedset could be a good option than Hashmap.

//tested code
int main ()
{
int a [26][2]; // [26] - possible_alpahabets
// [first index] - occurence count;
// [second index] - nth character in array.

//set the elements to 0;
for (int row= 0; row < 26; row++)
{
for (int col =0 ; col < 2; col++)
{
a [row] [col] = 0;
}
}


char str [] = {"eabexccdebfa"}; // 'x' should be the ans. we have 'd' and 'f' but not first of unique.
int length = (int) strlen (str);


//find the ascii value of every char

for (int iter = 0; iter < length ; iter++)
{
int ch = str [iter];
//to make the value fall within array of 26 characters.
int val = ch - 97; //97 - ascii value of 'a'.
a [val][0] += 1; //incrementing count of every character
a [val][1] = iter; //registering the nth character.
}

int asc = length;
char mych = '\0';
for (int two = 0; two < 26;two++)
{
//eliminating characters that has occurred more than once.
if (a [two][0] == 1 )
{
//we are looking for first unique value.
//lowest of the nth character registered using second index.
if ( asc > a[two][1])
{
asc = a[two][1];
mych = str [asc];
}
}
}
if (asc != length) //handling if there were no unique characters.
cout << mych << endl;
return 0;
}

My solution:
#include <iostream>
#include <string.h>
using namespace std;
typedef struct{
int time;
int pos;
}Htable;

int
FindUniqueChar(char Array[]){
Htable _hTable[256];
for(int i=0; i < 256; i++){
_hTable[i].time = 0;
_hTable[i].pos =-1;
}
for(unsigned i=0; i< strlen(Array); i++){
unsigned pos = static_cast<unsigned> (Array[i]);
if(_hTable[pos].pos< 0){
_hTable[pos].pos = i;
}
_hTable[pos].time ++;
}
int min_pos = -1;
for(int i=0; i < 256; i++){
if(_hTable[i].time == 1){
if(min_pos == -1){
min_pos = i;
}
else{
if(_hTable[i].pos < _hTable[min_pos].pos){
min_pos = i;
}
}
}
}
if(min_pos== -1){
return -1;
}
else{
return _hTable[min_pos].pos;
}
}

int
main(){
char A[] = "345483";
int pos = FindUniqueChar(A);
cout<<pos<<endl;
return 0;
}

struct htable 
{
       int pos;
       int count;
};

int main()
{
    struct htable hash[26];
    struct htable ans;
    
    int i = 0;
    char str[] = "abcdefghbcdef";    
    int pos = 500000; //some large number
    
    for (i=0; i< 26; i++)
    {
        memset(&hash[i],0, sizeof(struct htable));
    }
    
    for(i=0; i < sizeof(str); i++)
    {
           if (!hash[(int)(str[i] - 'a')].pos)
           {
                                  hash[(int)(str[i]-'a')].pos = i;
                                  hash[(int)(str[i] - 'a')].count++;
                                  continue;
           }
           
           else hash[(int)(str[i] - 'a')].count++;
           
    }  
    
    
    for (i = 0; i<26; i++)
    {
          if( hash[i].count == 1) 
          if (ans.pos > hash[i].pos) ans.pos = hash[i].pos;
          continue;
        
    }
    
    printf("%c", str[ans.pos]);
    
    
    getch();

}

I came across a similar question to this one - it used integers instead of chars but the logic works just the same. I wrote my code in Java but you can port it easily enough.

public static char findFirstUnique(char[] sequence)
	{
		HashMap<String, Integer> map = new HashMap<String,Integer>();
		for(char letter : sequence)
		{
		if(map.containsKey(String.valueOf(letter)))
				map.put(String.valueOf(letter),map.get(String.valueOf(letter))+1);
		else
			map.put(String.valueOf(letter), 1);
		}
		for( char letter: sequence)
		{
			
			if(map.get(String.valueOf(letter))==1)
				return letter;
			
		}
		return '-';
	}

Code is tested and works had to use String because Maps in Java don't allow for primitive types.