nikinjain
BAN USER
Comments (4)
Reputation 60
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
3
of 3 vote
You can solve this problem in two ways. Use a recursive approach or a memoization technique in dynamic programming.
First, technique discusses the recursive approach, here's the code.
int lcs(char *x, char *y, int m, int n)
{
if(m==0 || n==0)
return 0;
if(x[m-1] == y[n-1])
return 1 + lcs(x,y,m-1,n-1);
else
return max(lcs(x,y,m,n-1), lcs(x,y,m-1,n));
}
Second approach discusses the memoization method of DP. Here's the code
int lcs(char *x, char *y, int m, int n)
{
int lcs[m+1][n+1];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0 || j==0)
lcs[i][j] = 0;
else if(x[i-1] == y[j-1])
lcs[i][j] = lcs[i-1][j-1] + 1;
else
lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j]);
}
}
return lcs[m][n];
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Deadlock, Processor Hogging, Starvation
- nikinjain February 28, 2013