Amazon Interview Question Software Engineer / Developers
0of 0 votesFind the longest common subsequence of two string
Country: United States
Interview Type: Phone Interview
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];
}
standard solution :
use dynamic programming with
M[i][j] = {1+M[i-1][j-1] if A[i] ==B[j]}
{max(M[i][j-1],M[i-1][j]) otherwise}
@sonesh, are you assuming that subsequences can be non-contiguous? If the two strings are "X****Y***Z" and "X______Y__Z", I think your method will return 3, which is valid under the non-contiguous interpretation.
dynamic programming approach
time complexity:O(len(a)*len(b))
int LCS(string& a,string& b)
{
int m = a.length();
int n = b.length():
vector<vector<int>>dp (m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i-1] == b[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
public class subsequence {
public void method(String a, String b)
{
String s1 = a;
String s2 = b;
int arr1[] = new int[255];
for(int i =0; i< s1.length(); i++){
arr1[s1.charAt(i)] = arr1[s1.charAt(i)] + 1;
}
for(int i=0; i<s2.length(); i++){
if(arr1[s2.charAt(i)]!=0){
arr1[s2.charAt(i)]--;
System.out.println(s2.charAt(i));
}
}
}
public static void main(String[] args) {
int[] arr = new int[256];
subsequence s = new subsequence();
//s.method({'k', 'r','i'}, )
s.method("abc", "abcd");
}
}
package com.careercup;
public class StringSubSequence {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
StringSubSequence stringSubSequence = new StringSubSequence();
System.out.println(stringSubSequence.subsequence("abcdefgh", "cdefg"));
//System.out.println(stringSubSequence.subsequence("abcdfgh", "asdfdfabcdf"));
}
public String subsequence(String string1, String string2){
StringBuffer subsequence = new StringBuffer("");
String shortString= null;
String longString = null;
if(string1.length() > string2.length()){
shortString = string2;
longString = string1;
}
else{
shortString = string1;
longString = string2;
}
int shortStringLength = shortString.length();
int longStringLength = longString.length();
int shortStringCounter =0;
int longStringCounter =0;
StringBuffer tempsb = new StringBuffer();
while(shortStringCounter < shortStringLength){
longStringCounter = 0;
while(longStringCounter < longStringLength){
if(shortString.charAt(shortStringCounter) == longString.charAt(longStringCounter)){
tempsb = new StringBuffer();
int compare1Counter = shortStringCounter;
int compare2Counter = longStringCounter;
do{
tempsb.append(shortString.charAt(compare1Counter));
compare1Counter++;
compare2Counter++;
}while(compare1Counter < shortString.length() && compare2Counter < longString.length() && (shortString.charAt(compare1Counter) == longString.charAt(compare2Counter)));
if(tempsb.length() > subsequence.length()){
subsequence = tempsb;
}
}
longStringCounter++;
}
shortStringCounter++;
}
return subsequence.toString();
}
}
public void findLongestSubsequence() {
String str="",max="";
String str1="lkjhgfds",str2="oiuyhgftr";
char [] arr1 = str1.toCharArray();
char [] arr2 = str2.toCharArray();
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr2.length; j++) {
if(arr1[i]==arr2[j]){
str="";
int k=0;
while((i+k)<arr1.length && (j+k)<arr2.length){
if(arr1[i+k]!=arr2[j+k])
break;
str=str+arr1[i+k];
k++;
}
if(max.length()<str.length())
max=str;
}
}
}
System.out.println("===="+max);
}
import java.util.Scanner;
public class StringSubsequence {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = new int[256];
String s1 = new String();
String s2 = new String();
Scanner scan = new Scanner(System.in);
s1=scan.next();
s2=scan.next();
int s1size = s1.length();
int i;
for(i=0;i<s1size ;i++){
a[(int)s1.charAt(i)]++;
}
int s2size = s2.length();
for(i=0;i<s2size;i++){
if(a[(int)s2.charAt(i)] != 0){
a[(int)s2.charAt(i)]--;
System.out.println(s2.charAt(i));
}
}
}
}
Time Complexity : O(m) + O(n)
nice work man but its not working..
it is calculating the sub string but it must be continues according to your logic.
Here is the solution
package com;
public class LongestSubSequence {
private static int startIndex = 0;
private static int length = 0;
static boolean foundStartIndex = false;
public static void main(String args[]) {
char[] firstStr = "AABBCDEF".toCharArray();
char[] secondStr = "AADEF".toCharArray();
for (int i = 0; i < firstStr.length; i++) {
int intrimindex = 0;
int intrimlength1 = 0;
foundStartIndex = false;
int counter = i;
for (int j = 0; j < secondStr.length; j++) {
if (firstStr[counter] == secondStr[j]) {
if (!foundStartIndex) {
intrimindex = setStartIndex(i);
}
intrimlength1++;
if (counter + 1 <= firstStr.length-1)
counter++;
else {
break;
}
} else {
if (foundStartIndex) {
foundStartIndex = false;
if (intrimlength1 > length) {
swapValues(intrimlength1, intrimindex);
}
}
}
}
if (intrimlength1 > length)
swapValues(intrimlength1, intrimindex);
}
System.out.println("AABBCDEF".substring(startIndex, startIndex + length
));
}
private static int setStartIndex(int i) {
int intrimindex;
intrimindex = i;
foundStartIndex = true;
return intrimindex;
}
private static void swapValues(int length1, int index) {
length = length1;
startIndex = index;
}
}
can someone tell me why my solution is stupid? i am using contains(), is that not allowed or does that make it much too slow?
public static String returnSubsequence(String one, String two)
{
HashMap<String,Integer> map = new HashMap<String,Integer>();
String sub = "";
int maxLength =0;
String maxSub = "";
for(int i = 0; i<one.length();i++)
{
sub += Character.toString(one.charAt(i));
// System.out.println(sub);
if(two.contains(sub) && sub.length() >= maxLength)
{
maxSub = sub;
maxLength = sub.length();
}
else
{
sub = Character.toString(sub.charAt(sub.length()-1));
}
}
//for()
return maxSub;
}
can someone tell me why my solution is stupid? i am using contains(), is that not allowed or does that make it much too slow?
public static String returnSubsequence(String one, String two)
{
HashMap<String,Integer> map = new HashMap<String,Integer>();
String sub = "";
int maxLength =0;
String maxSub = "";
for(int i = 0; i<one.length();i++)
{
sub += Character.toString(one.charAt(i));
// System.out.println(sub);
if(two.contains(sub) && sub.length() >= maxLength)
{
maxSub = sub;
maxLength = sub.length();
}
else
{
sub = Character.toString(sub.charAt(sub.length()-1));
}
}
//for()
return maxSub;
}
standard solution :
use dynamic programming with
- sonesh February 27, 2013M[i][j] = {1+M[i-1][j-1] if A[i] ==B[j]} {max(M[i][j-1],M[i-1][j]) otherwise}