Adobe Interview Question
Computer ScientistsCountry: India
Interview Type: In-Person
All possible combination of the string those are in increasing sequence of index can be made and the max length one will be the answer. The complexity will be n2.
public class Test {
static int size;
static String sequence;
static boolean check;
public static void main(String args[]){
System.out.println("Enter the first string");
Scanner scanner=new Scanner(System.in);
String str1=scanner.next();
System.out.println("Enter the second string");
String str2=scanner.next();
if(str1.length()<=str2.length()){
findSubSequence("",str1.toCharArray(),str2.toCharArray(),0);
System.out.println(sequence+" "+size);
}
else{
findSubSequence("",str2.toCharArray(),str1.toCharArray(),0);
System.out.println(sequence+" "+size);
}
}
public static void findSubSequence(String seq,char arr1[],char arr2[],int index){
String prevSeq=seq;
for(int l=index;l<arr1.length;l++){
findSubSequence(prevSeq+arr1[l],arr1,arr2,l+1);
if(findINSTR(new String(arr2),seq))
set(seq);
seq+=arr1[l];
}
}
public static boolean findINSTR(String k,String seq)
{
char arr[]=seq.toCharArray();
char arr2[]=k.toCharArray();
String str="";
int in=0;
for(int l=0;l<arr2.length;l++)
if(in<arr.length&&arr2[l]==arr[in]){
in++;
str+=arr2[l];
}
if(str.equals(seq))
return true;
return false;
}
public static void set(String seq){
if(!check||size<seq.length()){
check=true;
size=seq.length();
sequence=seq;
}
}
}
Made few changes...
public class Test {
static int size;
static String sequence;
static boolean check;
public static void main(String args[]){
System.out.println("Enter the first string");
Scanner scanner=new Scanner(System.in);
String str1=scanner.next();
System.out.println("Enter the second string");
String str2=scanner.next();
if(str1.length()<=str2.length()){
findSubSequence("",str1.toCharArray(),str2,0);
System.out.println("Sequence is:"+sequence+" size is:"+size);
}
else{
findSubSequence("",str2.toCharArray(),str1,0);
System.out.println("Sequence is:"+sequence+" size is:"+size);
}
}
public static void findSubSequence(String seq,char arr1[],String str,int index){
if(findINSTR(str,seq))
set(seq);
for(int l=index;l<arr1.length;l++)
findSubSequence(seq+arr1[l],arr1,str,l+1);
}
public static boolean findINSTR(String k,String seq)
{
char arr[]=seq.toCharArray();
char arr2[]=k.toCharArray();
String str="";
int in=0;
for(int l=0;l<arr2.length;l++)
if(in<arr.length&&arr2[l]==arr[in]){
in++;
str+=arr2[l];
}
if(str.equals(seq))
return true;
return false;
}
public static void set(String seq){
if(!check||size<seq.length()){
check=true;
size=seq.length();
sequence=seq;
}
}
}
Isn't the answer to the problem of finding the longest common sub-sequence from X="ZTANBMBLAUCY " and Y ="GABVCBKLAMNC" is ABBLAC and not ABBAC?
Here's the code to demonstrate the recursive method to find the LCS of two strings.
#include <stdio.h>
#include <string>
using std::string;
#define min(a, b) (a < b)
#define max(a, b) (a > b)
string LCS(const string& X, const string& Y)
{
int lx, ly;
string res;
string sx;
string sy;
lx = X.length();
ly = Y.length();
if (lx == 0 || ly == 0)
return "";
if (X[lx - 1] == Y[ly - 1]) {
sx = X.substr(0, lx - 1);
sy = Y.substr(0, ly - 1);
res = LCS(sx, sy) + X[lx - 1];
return res;
}
sx = LCS(X.substr(0, lx - 1), Y);
sy = LCS(Y.substr(0, ly - 1), X);
lx = sx.length();
ly = sy.length();
res = (lx > ly) ? sx : sy;
return res;
}
int main(int argc, char* argv[])
{
string X = "ZTANBMBLAUCY "; //"CATCG";
string Y = "GABVCBKLAMNC"; //"GTACCGTC";
printf("LX: %d LY: %d\n", X.length(), Y.length());
string res = LCS(X, Y);
printf("LCS: <%s> <%s> is: %s\n", X.data(), Y.data(), res.data());
return 0;
}
And the answer is:
LX: 13 LY: 12
LCS: <ZTANBMBLAUCY > <GABVCBKLAMNC> is: ABBLAC
Simple DP approach to this problem.
Correct me if any corner cases or mistakes
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stack>
using namespace std;
#define MAX(a,b) (a>b)?a:b
void LCS_DP(char s1[],char s2[]){
int l1,l2;
l1=strlen(s1);
l2=strlen(s2);
//create the look up table
int table[l1+1][l2+1];
for(int i=0;i<=l1;++i){
for(int j=0;j<=l2;++j){
if(i==0 || j==0){
//fill all start idx with 0
//to initialize
table[i][j]=0;
}
else{
//if chars match, then add 1 to the up-left idx val
if(s1[i-1]==s2[j-1]){
table[i][j]=table[i-1][j-1]+1;
}
//else fill with the larger value amongst the top or the left idx
else{
table[i][j]=MAX(table[i-1][j],table[i][j-1]);
}
}
}
}
//naturally the length of the lcs is the right bottom corner element
//display LCS length
cout<<"lcs length is "<<table[l1][l2]<<endl;
//now get the string, since it will be in reversed order
//hence maintain a stack to push elements
stack<char> mystack;
//start from the right most corner
int i=l1,j=l2;
while(i>0 && j>0){
//since this value dominates on both it top idx and left idx
//hence it must be a match, hence push in stack
if(table[i][j] > table[i-1][j] && table[i][j-1]){
mystack.push(s1[i-1]);
--i;--j;
}
//since they dont match proceed in the direction with max value
//if both equal then proceed in any direction
else{
if(table[i-1][j]>=table[i][j-1]){
--i;
}
else{
--j;
}
}
}
//finally display the stack elements
while(!mystack.empty()){
cout<<mystack.top();
mystack.pop();
}
return;
}
int main(){
char s1[]="ZTANBMBLAUCY";
char s2[]="GABVCBKLAMNC";
LCS_DP(s1,s2);
return 0;
}
This problem can be solved by using dynamic programming.
- coolsolution August 24, 2012Let X[1..m] and Y[1..n] be two arrays. Let LCS(i,j) = Length of longest common subsequence for subarrays X[1..i] and Y[1..j].
Then LCS(0,j) = 0 for all j
LCS(i,0)= 0 for all i
LCS(i,j) = 1 + LCS(i-1,j-1) if X[i]== Y[j]
LCS(i,j) = max ( LCS(i,j-1), LCS(i-1,j) ) if X[i]!= Y[j]
Now we can construct the two dimentional LCS[0..m][0..n] array from top to down and left to right so that we have the previous values.
For example X="ABA"
Y = "ACBA";
then we have to find LCS(3,4)
Now LCS(3,4) = 1 + LCS(2,3) as X[3]=Y[4]
Now LCS(2,3) = 1 + LCS(1,2) as X[2] = Y[3]
LCS(1,2) = max( LCS(0,2), LCS(1,1) ) as X[1] != Y[2]
LCS(0,2) = 0 and LCS(1,1) = 1+LCS(0,0) = 1 as X[1] = Y[1]
Hence LCS(1,2) = 1
LCS(2,3) = 2
LCS(3,4) = 3
To understand this solution you can take a look at following video
youtube.com/watch?v=wJ-rP9hJXO0