Adobe Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
Idea is like this
I have stored the index of the first occurrence of every element in the string, in array arr.
Then while traversing the array i have incremented the count on that index in array hash
Then we can check the first element in hash whose count is 1,
and its index would be the index of the first non-repeating element in the string
#include <stdio.h>
#include <limits.h>
void find(char *s)
{
int hash[256]={0},i,min=INT_MAX;
for(i=0;s[i];i++)
hash[s[i]]++;
for(i=0;s[i];i++)
{
if(hash[s[i]]==1 && i<min)
min=i;
}
if(min!=INT_MAX)
printf("First non-repeating character: %c",s[min]);
else
printf("No non-repeating character");
}
int main()
{
char ch[10];
fgets(ch,10,stdin);
find(ch);
return 0;
}
ideone.com/WuUQq
private static void FirstNonrepeatingCharacterinastring()
{
String inputstring = string.Empty;
Console.WriteLine("Enter the string : ");
inputstring = Console.ReadLine();
if (inputstring!=null)
{
char[] b = new char[inputstring.Length];
int[] hash = new int[256];
b = inputstring.ToCharArray();
for (int i = 0; i < inputstring.Length; i++)
hash[b[i]] = hash[b[i]] + 1;
for (int j = 0;j < inputstring.Length;j++)
{
if (hash[b[j]] == 1)
{
Console.WriteLine(b[j]);
break;
}
}
}
}
unsigned char arIndex[256]={0};
unsigned char buff[10] ={0};
strcpy( (char*)buff, "sbd3b2md");
unsigned int unLength = strlen((char*)buff);
unsigned int unCnt = 0;
while( unCnt < unLength )
{
arIndex[buff[unCnt]]++;
if ( arIndex[buff[unCnt]] > 1 )
{
cout << buff[unCnt];
break;
}
unCnt++;
}
# include<stdio.h>
# include<conio.h>
# include<string.h>
# define max 256
int hasht[max];
main()
{
int i,len;
char str[max];
printf("enter the string\n");
gets(str);
len=strlen(str);
for(i=0;i<len;i++)
{
hasht[(str[i])%256]=hasht[(str[i]%256)]+1;
}
for(i=0;i<len;i++)
{
if(hasht[str[i]%256]>1)
{
printf("leter that is rpeatd is :%c",str[i]);
break;
}
}
getch();
}
Time complexity : O(n)
Soace Complexity: O(n)
char FirstNonReaptChar( char *s)
{
int even= 0,odd = 0, l = 0, r=sizeof(s)-1;
int Hash[sizeof(s)]= {0};
if( sizeof(s) % 2 == 0)
{
even = 1;
}
else
odd = 1;
while(l<sizeof(s) && r >=0)
{
if (even || odd)
{
if(l<r)
{
Hash[(int)s[l]]++;
Hash[(int)s[r]]++;
l++;
r--;
}
}
if(odd && l==r)
{
Hash[(int)s[l]]++;
l++;
}
if(r<l)
{
if (Hash[r] == 1)
{
return s[r];
}
else if (Hash[l] == 1)
{
return s[l];
}
else
return 0;
l++;
r--;
}
}
}
Working Code
- Luv July 03, 2012