Microsoft Interview Question
Software Engineer in TestsActually, I think you can understand this question in another way, which the distance between the most nearest a and b <= distance or not
bool findABWithinDis(string s, char a, char b,int distance)
{
char c;
int firstPos = -1;
if((s.size()>1 )&& (distance < s.size()-2))
{
for(int i=0;i<s.size();i++)
{
if((firstPos > -1)&&(s[i]==c)&&(i-firstPos <=distance))
{
return true;
}
if(s[i] == a)
{
c = b;
firstPos = i;
}
else if(s[i] == b)
{
c = a;
firstPos = i;
}
}
}
return false;
}
and it is O(n).
// Assumptions: Null terminated string
// Test cases. If value of d is way to big then the code will return
// value of d cannot be -ve
// a and b can be same or different
// a and b can contain any values including '\0'
void func(char a,char b,char* str,int dist)
{
char t1,t2;
int flag=-1,count=dist,i=0;
// Distance cannot be less than or 0
if(dist<=0)
return ;
while(i+dist<strlen(str))
{
t1= str[i];
t2= str[i+dist];
if(t1==a)
flag=1;
else if(t1==b)
flag=2;
if(flag==1 && t2== b)
{
printf("Match found\n");
return;
}
else if(flag==2 && t2==a)
{
printf("Match found\n");
return;
}
flag=-1;
i++;
}
}
1.what if char a and b occurs multiple times, which means there are more than distances between them?
- Jackie October 18, 20092. it needs to be a to b or could be from b to a?