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
youtube.com/watch?v=wJ-rP9hJXO0

- coolsolution August 24, 2012 | Flag Reply
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;
}
}
}

- Anonymous August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 26, 2012 | Flag
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?

- dc360 August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes you are correct. Answer should be ABBLAC

- Rahul August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ashot madatyan June 26, 2013 | Flag
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 ?

- catlover September 13, 2012 | Flag Reply
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;

}

And the answer is:

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

- ashot madatyan June 26, 2013 | Flag Reply
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;
}

- jaiwardhan.live September 02, 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