|
You are given a string sequence and program need to output the number......
Microsoft Interview Questions and Answers
(Continued from previous question...)
31. You are given a string sequence and program need to output the number......
Question:
You are given a string sequence and program need to output the number of times consecutive character sequences happen for increasing sequence length. eg. aabbababbd has 2 sequences as a followed by a, b followed by b. The for sequence length 2, ab followed by ab at 5th position. This is to be coded in minimum complexity.
maybe an answer1:
void printSubStr(char *str)
{
if (NULL == str)
return;
char *p_str = str;
int length = strlen(str);
char *p_end = p_str+length;
for (int i = length/2;i > 0;i--)
{
p_str = str+i;
while ((p_end - p_str) >= i)
{
int j = 0;
for (j = 0;j < i;j++)
{
if (*(p_str+j) != *(p_str+j-i))
break;
}
if (j == i)
{
while (j)
printf("%c",*(p_str-(j--)));
j = i;
while (j)
printf("%c",*(p_str+i-(j--)));
printf("\n");
}
p_str++;
}
}
}
maybe an answer2:
if we have to "find the sub-string which is repeated highest number in this string and we need to return that highest number of times that sub string is repeated" then i think the unoptimized solution would be the following:
int printMaxRepSub(char * str)
{
int end_p=0, start_max_ind=-1, end_max_ind=-1, max=0, tmp_max_rep=0, length=strlen(str);
for(int i=0;i<length;i++)
{
end_p=(length-i)/2;
for (int j=0;j<=end_p;j++)
{
if((tmp_max_rep=find_rep(str,j,end_p))>max)
{
max=tmp_max_rep;
start_max_ind=j;
end_max_ind=end_p;
}
}
}
print_substr(str,start_max,end_max);
return max;
}
int find_rep(char* str,int x,int y)
{
int rep=0, start_check_ind=y+1, end_check_ind=y+1 + (y-x), length=strlen(str);
while(end_check_ind<=length)
{
int tmp_ind=x;
for(int i=start_check_ind; i<=end_check_ind;i++)
{
if(str[i]!=str[tmp_ind++])
return rep;
}
start_check_ind=end_check_ind+1+(y-x);
end_check_ind+=1+(y-x);
}
}
void print_substr(char* str,int x, int y)
{
printf("The substring with the highest number of sequent repetitions is:\n");
for(int i=x;i<=y;i++)
{
printf("%c",str[i]);
}
}
The solution above can be optimized by eliminating unnecessary calculation in advance. When i have more time i'll try to improve this solution.
(Continued on next question...)
Other Interview Questions
| 