Amazon Interview Question for Member Technical Staffs


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

- HardCode July 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kavita July 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 09, 2014 | Flag
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));

}

- sd July 05, 2014 | Flag Reply
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;

}

- Suraj July 06, 2014 | Flag Reply
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;

}

- Suraj July 06, 2014 | Flag Reply
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)));
}

- dato123 July 06, 2014 | Flag Reply
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);
        }
    }

- Anonymous July 10, 2014 | Flag Reply
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];
}

- iwanna July 10, 2014 | Flag Reply
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);
}

- rajvishal777 July 15, 2014 | Flag Reply
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)){
						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.
*/

- Avishek Gurung July 21, 2014 | Flag Reply
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"));
	}

- Steve August 04, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More