Write an algorithm to find the first non-repeated character ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
50. Write an algorithm to find the first non-repeated character ......
Question:
Write an algorithm to find the first non-repeated character in a string using O(1) space and O(n) time. you can only use 1 bit space for each character.
maybe an answer:
The first is incorrect, update, Please see following code
int Find1stNonRepeated(TCHAR str[], int nLen)
{
int nCurPos = 0;
BOOL bRepeat = FALSE;
while(nCurPos + 1 != nLen)
{
bRepeat = FALSE;
for(int n=0;n<nCurPos; n++)
{
if(str[n] == str[nCurPos])
{
bRepeat = TRUE;
break;
}
}
if(!bRepeat)
{
for(int i = nCurPos +1 ; i< nLen; i++ )
{
if(str[i] == str[nCurPos])
{
bRepeat = TRUE;
break;
}
}
}
if(!bRepeat)
{
wprintf_s(L"Found the non-repeated char : %c in pos %d", str[nCurPos], nCurPos);
return nCurPos;
}
else
{
nCurPos++;
}
}
wprintf_s(L"Can't Found the non-repeated char \n");
return -1;
}
maybe an answer2:
char find(char str[], int len)
{
for(int i=0;i<len;i++)
{
if( bitmap & 1<<(str[i] - 'a'))
{
bmp = bmp | 1<<(str[i]-'a');
}
else
{
bitmap = bitmap | 1<<(str[i] - 'a');
}
}
bitmap = bitmap ^ bmp;
int i=0;
while( !(bitmap&1) )
{
bitmap=bitmap>>1;
i++;
}
return 'a' + i;
}
(Continued on next question...)
Other Interview Questions
|