Microsoft Interview Question Software Engineer / Developers
actually this question was asked in microsoft written paper in my college on 2nd august. the solution using two variables is the correct solution of the problem as per the interviewer (he asked it again in interview and then he gave a hint to use two variables and later confirmed its correctness himself!). from past 3 days i am trying to optimize it to use only one variable but finally i have figured out that one cannot do it in less than 2 variables because we need to represent 3 states (non-repeated, repeated & not present) and we cannot do this in binary since binary represents only 2 states. that's my observation till now and i would be happy if someone wrongs me :)
You don't need three states. 0 can indicate that it is not present. when you first hit this char, mark it 1. Before you mark anything, check it if it is already 1, again by OR. If it is, just return that char.
You don't need three states. 0 can indicate that it is not present. when you first hit this char, mark it 1. Before you mark anything, check it if it is already 1, again by OR. If it is, just return that char.
You don't need three states. 0 can indicate that it is not present. when you first hit this char, mark it 1. Before you mark anything, check it if it is already 1, again by OR. If it is, just return that char.
@anon: i think as per your method, we find the first repeated character and not first non-repeated. correct me if i am wrong on that.
int var=0;
for(int i=0;str[i]!='\0';i++)
{
if(!(var&1<<(str[i]-'a')) var|=1<<str[i]-'a';
else var=var&(~(1<<(str[i]-'a'));
}
for(int i=0;str[i]!='\0';i++)
{
if((var&1<<(str[i]-'a')) print; break;
}
i think this should work
@codez nice thought ..... :)
As unset bit of a character can represent both of its absence or its repetition , As we are concerned only about the first occurrence of a non-repeated character we can simply check the first character in the string which is set in the variable var by the second for loop .
public string getFirstUnrepeatedChar(string str)
{
string noRepeat;
int firstIndex = 0;
int lastIndex;
str = str.ToLower();
for (int i = 0; i < str.Length; i++)
{
noRepeat = str.Substring(i, 1);
firstIndex = str.IndexOf(noRepeat);
lastIndex = str.LastIndexOf(noRepeat);
if (firstIndex == lastIndex)
break;
}
return str.Substring(firstIndex, 1);
}
It will come out of the loop in the very first iteration with no output.
At least put something her after running couple of dry run with different types of input.
Wasting everybody's time for nothing.
void FindFirstNonRepeatChar(TCHAR* pIn, int& nPos)
{
if (NULL == pIn)
{
return;
}
TCHAR* pHead = pIn;
int nIndex = 0;
BOOL bFound = FALSE;
TCHAR* pFoot =pIn + wcslen(pIn) - 1;
do
{
if (pHead[0] ==pFoot[0])
{
pHead++;
nIndex ++;
pFoot = pIn + wcslen(pIn) - 1;
}
pFoot--;
} while (pHead != pFoot);
if (pHead == pFoot && pHead != pIn + wcslen(pIn) -1)
{
nPos = nIndex;
TCHAR szNonRepeat = (pIn+6)[0];
wprintf_s(L"Found the non-repeated char : %c in pos %d", szNonRepeat, nPos);
}
getchar();
}
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;
}
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;
}
This Solution seems to be perfect. a little bit of commenting would have saved a lot of time in understanding.
Thanks a lot though. :)
sorry for not putting comments. it is basically same implementation explained by above by sid_gup.
There is a correction here though because this program will fail for input like "abcdkeabcd". The while loop at bottom will be changed to -
int i=0;
while( ! (bitmap & 1<<(str[i] - a)) )
i++;
return str[i];
Without this correction the program was finding the unique element with lowest ascii value rather than the first unique element.
Hence the above modification goes one more through the array to find the firstmost character which is set as unique in the bitmap.
Nice logic:) But I have a question, how wud you represent the Bitmap and bmp?? as a array of bits whose size is the number of characters?? and wud that still be 0(1) space complexity? I am not able to figure this out!!
public char firstNonRepeatChar(String str){
int[] array = new int[255];
//set array[1-non repeating, 1<-repeating]
for(int i=0;i<str.length;i++){
int c=(int)str.charAt(i);
if(array[c]>=1){//check for repeat values
array[c]++;//increment
}
else{
array[c]=1;
}
}
//check for first non repeating one
for(int i=0;i<str.length;i++){
int c=(int)str.charAt(i);
if(array[c]==1){
return str.charAt(i);
}
}
}
it's simple
suppose the input string is "str"
take one dictionary (or) hastable
strig str = "string";
dict<string,int> dict = new dict<string,int>();
for(int i=0;i<str.Length-1;i++)
{
if( dict.Contains(str[i])
{
int count = dict(str[i]);
dict(str[i]) = count++;
}
else
{
dict(str[i]) = 1;
}
}
print the dict based on the count value '1' which occured only once.
string str;
freopen("in.txt","r",stdin);
cin>>str;
int presentflag=0x0000;
int repeatflag=0x0000;
for(int i=0;i<str.size();i++)
{
int bitset=1<<str[i]-'a';
if(presentflag&bitset)
repeatflag|=bitset;
presentflag|=1<<str[i]-'a';
}
repeatflag=~repeatflag;
int result=presentflag&repeatflag;
for(int i=0;i<str.size();i++)
{
int bitresult=result&(1<<(str[i]-'a'));
if(bitresult>0)
{
cout<<str[i]<<endl;
break;
}
}
Just maintain two bitset of size equal to the number of possible characters i.e. 256.
The first bitset will have information that the character is present of not and second bitset will have information that it is repeted or not. Then find first character satisfying the condition that present and not-repeated.
I think it is possible to do it using 1 bit for every char.
1.traverse the array, mark the corresponding bit as 1 if it occurs for the 1st time. And mark it 0 if its value is 1 previously(that means it has occurred more than 1 time)
2. Traverse the array again, the character with 1st bit as 1 is the answer. If u encounter a value 0 that means that char has occurred more than once(bcoz it has surely present in the array as we have already done the 1st pass).
<pre lang="" line="1" title="CodeMonkey48728" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(" index is= " + getNonRepeatedChracterStartIndex("helojii"));
}
public static int getNonRepeatedChracterStartIndex(String str)
{
if(str!=null && str.length()>0)
{
char previousCharstr=str.charAt(0);
int length=str.length();
for(int index=1;index<length;index++)
{
char currentChar=str.charAt(index);
if(previousCharstr==str.charAt(index))
{
return index-1;
}
previousCharstr= currentChar;
}
}
return -1;
}
}
</pre><pre title="CodeMonkey48728" input="yes">
</pre>
So many flaws...
It should return character but it does return index.
It returns repeated character only whereas it should do the opposite.
And the comparison is only between consecutive characters.
So this program is only good for returning Index of first consecutively repeated character.
well we can traverse the list in the reverse order and find the last unrepeated charector and i think that give us the first nonrepeated charector in the given string.
Now there's some thought !!
And here's some melody :
#include<stdio.h>
void main(){
char str[] = "abcdkabcd";
int len=sizeof(str)-1;
int i,mem=0;
char myBitch;
for ( i=len-1 ; i>=0 ; i-- )
if (!((1<<(str[i]-'a'+1)) & mem )){
myBitch=str[i];
mem|=(1<<(str[i]-'a'+1));
}
printf("%c\n",myBitch);
}
I think below solution should work fine.
- Anonymous August 05, 20111) take a integer say pint ( 32-bit ) will hold all 27 characters assuming string contains only letters ( case insensitive ). setting each bit represents the letter is present or not in a string,
2) take another integer rint for storing whether the character is repeated or not.
3) tranverse through string and set bit in the pint, if pint is already set that means the character is repeated. so set the bit in the rint.
4) Traverse string again to see whether the bit for the character is set in the rint.
if set that means character is repeated continue till u find a character which is not repeated.