CareerCup

I totally do not grasp the question you were asked.

> "...output the number of times consecutive character sequences happen..."
Good so far

> "...for increasing sequence length..."
What? What sequence is increasing in length? I am given a string sequence. That sequence is not going to increase, is it?

> "..aabbababbd has 2 sequences as [aa], [bb].."
I think I understand this phrase. I am not sure how it relates to the question asked.

> "The for sequence length 2"
Whoa! Try saying this part again - ?

> "...ab [follows ab] at 5th position."
Ok, this portion makes some sense.

> "This is to be coded in minimum complexity"
I do not know what is supposed to be coded based on this description.
Are we looking for an implementation of strstr(char*,char*)?

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..

i think i got it hurray !!!!
now please tell me the solution

Still did not get what need to be output. the substring that repeats for the highest number of time or the substring with the highest character count that gets repeated? A humb;e request to the question submitter to clarify that.

Everytime microsoft asks an interview question, gods kill seven kittens.
I expect no less stupid questions from Microsoft, they somehow live up to my expectations, poor kittens.
The solution for all problems is #include "windows.h" and your life becomes half.

I think this is the problem ask for appearence of contiguous pattern, for example, axyzxyza. for each character, no contiguous one is the same. But for patter "xyz", we can find another "xyz" follows. Thus the output is pattern "xyz" and number 2.

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.

Construct a suffix tree .. Sort the suffixes .. Find the i such that Xi to Xj has maximum length prefix .. O(nlogn) solution

suffix tree is a gud choice but can be done using suffix array also :)

Rephrasing... find Longest common substring in any 2 substrings(s1 and s2) of s such that s1+s2 = s. Am i correct understanding the question?

O(n^3) if memoization used

S(i, j)
	if(i < 0 || j<0)
		return 0
	else
		if(a[i] == a[j])
			return S(i-1, j-1)+1
		else
			return 0
CS()
	for each k from 0 to n-1
		for each i from 0 to k
			for each j from k+1, n-1
				v = S(i, j)
				if(v > max)
					max = v
	return max

can be done using DP

take an array a[26][26]=0;
taking the eg:
abbababcd
tring len=n;
size[0-n]=0;
for(int i=1;i<strlen();i++)
{ if(s[i-1]+1=s[i])
{
  size[i]=size[i-1]+1;
 a[s[i]-size[i]-'a'][size[i]]++;
}}
for(i=0;i<26;i++)
{ for(j=0;j<26;j++)
           {         if(a[i][j]!=0)
                     {
                        cout<<"sequence from start= "<<i+'0'<<" to end= "<<i+j+'0'<<" no. of times= "<<a[i][j]<<"\n";
                     }
           }
}

because of two scanf function fist scan f will ocuppy the buffer

<pre lang="" line="1" title="CodeMonkey41025" class="run-this">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++;
}
}
}
</pre><pre title="CodeMonkey41025" input="yes">
</pre>