## Adobe Interview Question for Computer Scientists

Country: India
Interview Type: In-Person

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

This problem can be solved by using dynamic programming.
Let 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

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

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

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

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

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

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?

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

Yes you are correct. Answer should be ABBLAC

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

Yes, that's correct, the answer is: "ABBLAC"

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

Isn't it the famous LCS problem ? geeksforgeeks.org/archives/12998
I am surprised that they can ask this directly, no ?

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

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

}

``````LX: 13 LY: 12
LCS: <ZTANBMBLAUCY > <GABVCBKLAMNC> is: ABBLAC``````

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

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

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.