## Amazon Interview Question for Member Technical Staffs

• -2

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

int lcs( char *str1, char *str2, int m, int n )
{
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));
}

Comment hidden because of low score. Click to expand.
0

``````Wrong solution i am sure it not give correct result
abcebcdf
abbcdx
here lcs is bcd only and your solution not give 3 length``````

Comment hidden because of low score. Click to expand.
0

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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)));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)){
}
}

}

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.
*/``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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"));
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.