MAGMA Interview Question
Software Engineer / DevelopersInterviewer told me, we can solve this problem in two ways 1. Brute force 2. Dynamic programming . After that he explained Brute Force method .
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.
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)
1. I could not answer this question. Interviewer explained me the possible answer.
- siva.sai.2020 February 17, 20112. 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) )