Amazon Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
Wrong solution i am sure it not give correct result
abcebcdf
abbcdx
here lcs is bcd only and your solution not give 3 length
int lcsuffix(int **mat, char *a, int m, char *b, int n)
{
if(m < 0 || n < 0)
return 0;
if(mat[m][n] != INF)
return mat[m][n];
if(a[m] != b[n])
mat[m][n] = 0;
else
mat[m][n] = 1 + lcsuffix(mat, a, m-1, b, n-1);
return mat[m][n];
}
int lcstr(char *a, int m, char *b, int n)
{
int i, j, maxval = -100, val, **mat;
mat = (int **)malloc(m * sizeof(int *));
for(i = 0; i < m; i++)
{
mat[i] = (int *)malloc(n * sizeof(int));
for(j = 0; j < n; j++)
mat[i][j] = INF;
}
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
{
val = lcsuffix(mat, a, i, b, j);
maxval = max(maxval, val);
}
return maxval;
}
int LCS(char *str1, int len1, char *str2, int len2) {
int n1, n2;
n1 = strlen(str1);
n2 = strlen(str2);
if (n1 <= 0 || n2 <= 0) {
return 0;
}
if (n1 < len1 && n2 < len2) {
if (*str1 == *str2) {
return 1 + LCS(str1 + 1, len1 - 1, str2 + 1, len2 - 1);
}
else
return 0;
}
if (*str1 == *str2) {
return max(1 + LCS(str1 + 1, len1, str2 + 1, len2), LCS(str1, len1, str2+1, len2 - 1), LCS(str1 + 1, len1 - 1, str2, len2));
}
return max(LCS(str1, len1, str2+1, len2 - 1), LCS(str1 + 1, len1 - 1, str2, len2));
}
public static String lcs(String first, String second){
if (first.equals(second)) {
return first;
} else if (first.isEmpty() || second.isEmpty()) {
return "";
}
else {
String[] v = new String[4];
v[0]= lcs(first, second.substring(0,second.length()-1));
v[1]= lcs(first, second.substring(1,second.length()));
v[2]= lcs(first.substring(0,first.length()-1), second);
v[3]= lcs(first.substring(1,first.length()), second);
String temp =v[0];
for (int i = 1; i<v.length; i++){
if (temp.length()<v[i].length())
temp =v[i];
}
return temp;
}
In Java:
public static String lcs(String first, String second){
if (first.equals(second)) {
return first;
} else if (first.isEmpty() || second.isEmpty()) {
return "";
}
else {
String[] v = new String[4];
v[0]= lcs(first, second.substring(0,second.length()-1));
v[1]= lcs(first, second.substring(1,second.length()));
v[2]= lcs(first.substring(0,first.length()-1), second);
v[3]= lcs(first.substring(1,first.length()), second);
String temp =v[0];
for (int i = 1; i<v.length; i++){
if (temp.length()<v[i].length())
temp =v[i];
}
return temp;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int max(int a, int b){
if (a>b) return a;
else return b;
}
//abcdabc123 abjjdabcfhdbc123dju
int LCS(char *str1, int n, char *str2, int m){
if (n == 0){
return 0;
}
int max_len = 0;
int c_len = 0;
int i = 0;
int j = 0;
while (*(str1 + i) != '\0' && *(str2 + j) != '\0'){
if (*(str1 + i) == *(str2 + j)){
c_len++;
i++;
j++;
}
else {
if (c_len > 0 && c_len > max_len){
max_len = c_len;
c_len = 0;
}
i = 0;
j++;
}
}
if (c_len > 0 && c_len > max_len){
max_len = c_len;
}
//printf ("str1 %s str2 %s max_len %d\n", str1, str2, max_len);
return max(max_len, LCS(str1 + 1, n - 1, str2, m));
}
int main() {
char *str1 = "abcdabc123";
char *str2 = "abjjdabcfhdbc123dju";
printf("max LCS is %d\n", LCS(str1, strlen(str1), str2, strlen(str2)));
}
public int lcs(String a, int longestStreak, String b, int currentStreak) {
if (longestStreak < currentStreak)
longestStreak = currentStreak;
if (a.length() == 0 || b.length() == 0)
return longestStreak;
if (a.charAt(0) == b.charAt(0)) {
return lcs(a.substring(1), longestStreak, b.substring(1), currentStreak+1);
} else {
return lcs(a.substring(1), longestStreak, b.substring(1), 0);
}
}
Dynamic programming solution :
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];
int i, j;
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
I think this approach might work...
Given two strings a and b
LCS(char *a,int n,char *b,int m)
{
L = 0;
if(a[0]==b[0])
{
//Taking case if sub-string starts from starting of both the strings
L = 1 + LCS(&a[1],n-1,&b[1],m-1);
}
//Covering 2 cases
//1 . 1st element of a is excluded
//2. 1st element of b is excluded
M = max(LCS(&a[1],n-1,b,m),LCS(a,n,&b[1],m));
return max(M,L);
}
class Practice{
public static void main(String args[]){
String str1 = "avishekgurung";
String str2 = "anupgurung";
System.out.println(LCS(str1,str1.length(),str2,str2.length()));
System.out.println();
}
public static String LCS(String str1, int n, String str2, int m){
if(n == 1 || m == 1){
return "";
}
if(str1.equals(str2)){
return str1;
}
for(int i=0; i <= n-m; i++){
int x = i;
String top = "";
for(int j=0; j < m; j++){
top = top + str1.charAt(x);
x++;
}
String bottom = "";
for(int k=0; k<= str2.length() - m; k++){
int y = k;
bottom = "";
for(int l = 0; l < m; l++){
bottom = bottom + str2.charAt(y);
y++;
}
//System.out.println(top+" "+bottom);
if(top.equals(bottom)){
return top;
}
}
}
String output = LCS(str1,n,str2,m-1);
return output;
}
}
/*
Here understand the window is very important.
We must remember that the window size should be same for processing both strings str1 and str2.
For every substring that we generate from str1 of size m, we generate all possible substrings from str2 of size m and compare.
*/
// lcs(a,b) -- never touch b
// If a is a substring of b, return a
// else return the longer of lcs(a minus the 1st char, b) and lcs(a minus the last char, b)
public static String lcs(String a, String b) {
if (b.indexOf(a) != -1) return a;
String left = lcs(a.substring(1),b);
String right = lcs(a.substring(0,a.length()-1),b);
return left.length() > right.length() ? left : right;
}
public static void main(String[] args) {
System.out.println(lcs("ab","6a8b7"));
System.out.println(lcs("6a8b7","ab"));
System.out.println(lcs("abcdefg","67bcde9282929"));
System.out.println(lcs("67bcde9282929","abcdefg"));
}
int lcs( char *str1, char *str2, int m, int n )
- HardCode July 04, 2014{
if (m == 0 || n == 0)
return 0;
if (str1[m-1] == str2[n-1])
return 1 + lcs(str1, str2, m-1, n-1);
else
return max(lcs(str1, str2, m, n-1), lcs(str1, str2, m-1, n));
}