CareerCup

1)create array of size 256.
2)initialize it with 0
3)loop on the given array of chars (use char as the index of output array)
4)check the content, if content is 0 change it to 1 otherwise this is the first repeated char. stop

this solution is order of n.

example:
given array is [12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98]
output array res[256] = all zero's
alg:
res[12] = 1
res[46] = 1
res[244] = 1
res[0] = 1
res[12] is 1 then stop 12 is the first repeated char

There can be more than one repeated element. There could also be no repeated elements.
Notice how the values range from 0-255, these are unsigned char.
First thing that came to my head was using a hash but its not necessary.
I used Java because that is what I am most comfortable with but I just shot myself in the foot with that decision since Java doesn't have built-in unsigned type support

Sort the array and then scan it keeping track of the previous value.
As soon as (current == previous), break!

There are several answers to it some require more computation and some require extra space. I guess the best way to do it is maintain an array corresponding to 256 characters and increment the values depending on how many times you have seen the charater...here is my version of code.I am using an array of 128 assuming characters to be alphanumeric.

#include<stdio.h>
void main()
{
	char str[100];
	int a[128];
	int flag = false;
	char * ptr;
	printf("Enter the string \n");
	ptr = gets(str);
	int i = 0;
	for(i=0;i<128;i++)
		a[i] = 0;
	i = 0;
	while(ptr[i] != '\0')
		a[ptr[i++]]++;
	i = 0;
	while(ptr[i] != '\0')
	{
		if(a[ptr[i]] == 1)
		{
			printf("The first Non repeating character is %c \n", ptr[i]);
			flag = true;
			break;
		}
		else 
			i++;
	}
	if(!flag)
		printf("There is no non repeating character in the string \n");
}

Well, basket sort is easiest solution. But more efficient solution should be to construct a binary search tree from the array. before you go all the element, you should find the repeat one. Otherwise, there is no repeat one.

Just use a separate array of 256 short entries initialized to 0.
For each character increment the corresponding entry. If Entry is 2 then that's the character that is repeating first. Here is the function that returns the character:

char firstChar(char str[], int size){
short count[256];
int i = 0;
while (i<256) count[i++]=0;
for (i = 0;i<size; i++) {
char temp = str[i];
short j = (short) temp;
if (++count[j] == 2)
return temp;
}
return '\0';
}

gauravk.18 's answer is the standard approach for this kinda problem @ momo

consider the 1st elem as root of BST and start elems from array one by one.. if while adding if you get a duplicate elem => this is your ans...

1)create array of size 256.
2)initialize it with 0
3)loop on the given array of chars (use char as the index of output array)
4)check the content, if content is 0 change it to 1 otherwise this is the first repeated char. stop

this solution is order of n.

example:
given array is [12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98]
output array res[256] = all zero's
alg:
res[12] = 1
res[46] = 1
res[244] = 1
res[0] = 1
res[12] is 1 then stop 12 is the first repeated char

1)create array of size 256.
2)initialize it with 0
3)loop on the given array of chars (use char as the index of output array)
4)check the content, if content is 0 change it to 1 otherwise this is the first repeated char. stop

this solution is order of n.

example:
given array is [12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98]
output array res[256] = all zero's
alg:
res[12] = 1
res[46] = 1
res[244] = 1
res[0] = 1
res[12] is 1 then stop 12 is the first repeated char