CareerCup

1. I could not answer this question. Interviewer explained me the possible answer.

2. str1[] length is n
str2[] length is m

3. find all combinations of str1 i.e 2^n .

e.g 1) n = 2 , str1 = "AB"
possible combinations { "","A", "B","AB" }
total 4 combinationsi.e 2^2
e.g 2) n=3, str1 ="ABC"
Possible combinations {"","A","B","C","AB","AC","BC","ABC" } .
total 8 combinationsi.e 2^3

4. find all combinations of str2 i.e 2^m .

5. now have to match each str1 combination with str2 combination .
If it matches and greater than Previous matched string length, then store it as a best match. Otherwise goto next match.

6. Time complecxity O(2^n * 2^m) = O(2^(m+n) )

Isnt this just a Longest Common Subsequence question (unless I am missing something).It has a simple dynamic solution.

Perform dynamic programming on two strings as below.

Subseq(i,j) = max(Subseq(i,j-1),Subseq(i-1,j),{SubSeq(i,j)+1 if(a[i] == b[j]})

^I cant make head or tail of this statement. could you please explain a little more?
Thanks.

str1: ABCDEF
str2: ZACYEFX
Largest common sequence : ACEF

Approch:

1#Take two pointer ptr1 and ptr2 pointing to first char of strings(str1 ,str2).
2#check whether both of the pointer pointing to same char.
3#if YES then append the char into a new string 'commenSTR' and move both of the pointer to next char.
4#if NOT
4.1#check pointer PTR2 is pointing to null.If YES move pointer PTR1 to next and PTR2 to first char of STR2.Repeat from step-2.
4.2#check pointer PTR1 is pointing to null.If YES return 'commenSTR'.
4.3#move pointer str2 to next and Repeat from step-2.

en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example

This is straight out of CLR. i am surprised at interviewers answer..did he mention he was giving brute force?

int LCS[1024][1024];

int LongestCommonSubsequence( char pattern1[], int m, char pattern2[], int n)
{
	if ( m >= 1024 || n >= 1024)
	{
		printf("\n too long pattern \n");
		return -1; // return error -1
	}
	else
	{
		int i=0,j=0;

		while(i<m)
		{
			LCS[i++][n] = 0;
		}
		while(j<n)
		{
			LCS[m][j++] = 0;
		}

		for( i = m-1; i>= 0 ; i-- )
		{
			for( j= n-1; j>=0 ;j--)
			{
				LCS[i][j] = LCS[i+1][j+1];

				if(Pattern1[i] == pattern2[j] )
					LCS[i][j]++;

				if( LCS[i+1][j] > LCS[i][j] )
					LCS[i][j] = LCS[i+1][j];
				if(LCS[i][j+1] > LCS[i][j])
					LCS[i][j] = LCS[i][j+1];
			}
		}
		return LCS[0][0];
	}
}

Time complexity O(mn)