Interview Questions

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