Alcatel Lucent Interview Question for Developer Program Engineers


Country: India
Interview Type: In-Person




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

Let's intial value of answer to longest common subsequence(LCS) of s1 and s2
ans = LCS(s1,s2)

Now we have to add remaining characters of s1 and s2 into ans. This could be done greedily.

Here's why and how:
assume that LCS(s1,s2) = abc

So s1 and s2 should be something like these:
s1= (x1) a (x2) b (x3) c (x4)
s2= (y1) a (y2) b (y3) c (y4)

in which (xi) and (yi) could be any strings of any size(>=0)

Obviously, all of the characters of (xi) and (yi) are different, because otherwise we could extend LCS and get a bigger one which is a contradiction to the definition of LCS.

So now we could add all characters of xi and yi in any order to the answer.
so the answer would be:

ans = (x1)(y1) a (x2)(y2) b (x3)(y3) c (x4)(y4)

and finding the LCS is a classic Dynamic Programming problem which could be solved in O(N*M).

The length of S3 would be S1.size()+S2.size()-LCS.size(), which is the minimum size we could get, so this would be the best answer.

So the final time complexity would be O(N*M)

I really enjoyed the problem very much.

//Mehrdad AP

// finding LCS (by DP) and add remainig character between lcs greedily.
//Time Complexity: O(N*M)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string LCS(string s1,string s2)
{

	int N=s1.size(),M=s2.size();
	vector< vector<int> > dp(N),parent(N);
	for (int i=0;i<N;i++){
		dp[i].resize(M);
		parent[i].resize(M);
	}

	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			int maxi=0,par=1;

			if (i!=0 && dp[i-1][j]>maxi){
				maxi = dp[i-1][j];
				par = 1;
			}
				 
			if (j!=0 && dp[i][j-1]>maxi){
				maxi = dp[i][j-1];
				par = 2;
			}


			if (s1[i]==s2[j]){
				if (i!=0 && j!=0 && dp[i-1][j-1]+1>maxi){
					maxi = dp[i-1][j-1]+1;
					par = 3;
				}
				if (1>maxi){
					maxi = 1;
					par=3;
				}
			}

			dp[i][j] = maxi;
			parent[i][j]=par;
		}
	}

	int i=N-1,j=M-1;
	string ans="";
	while (i>=0 && j>=0){
		int par =parent[i][j];
		if (par==3){
			ans+=s1[i];
			i--,j--;
		}
		else if (par==2)
			j--;
		else if (par==1)
			i--;

	}
	reverse(ans.begin(),ans.end());

	return ans;

}



string findingMix(string s1,string s2)
{

	string lcs=LCS(s1,s2);

	int i=0,j=0;
	string ans="";

	for (int k=0;k<lcs.size();k++){
		while (i<s1.size() && s1[i]!=lcs[k]){
			ans+=s1[i];
			i++;
		}

		while(j<s2.size() && s2[j]!=lcs[k]){
			ans+=s2[j];
			j++;
		}

		ans+=lcs[k];
		i++,j++;
	}

	//finishing s1 and s2 characters
	while (i<s1.size()){
			ans+=s1[i];
			i++;
		}

	while(j<s2.size()){
		ans+=s2[j];
		j++;
	}

	return ans;
}


int main()
{

	string s1,s2;

	while (cin >> s1 >> s2){
		cout << findingMix(s1,s2) << endl;
	}

	return 0;
}

- MehrdadAP September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 3 votes

public class compareSubsequences
{
public static void main(String args[])
{
String s1 = "apple";
String s2 = "pear";
//String s3 = s1 + s2;
String s3;
s3 = new String(s1.substring(0, 4) + (s2.substring(1, 4)));
System.out.println(s3);}}

- Anonymous September 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

public class compareSubsequences{public static void main(String args[])
{String s1 = "apple";String s2 = "pear";String s3;
s3 = new String(s1.substring(0, 4) + (s2.substring(1, 4)));
System.out.println(s3);}}

- vicky September 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

string longestCommonSubsequence(const string& s1, const string& s2) {
  
  // Compute table of partial lengths of longest common SS's
  
  vector<vector<int>> partials(s2.size(), vector<int>(s1.size(), 0));
  
  partials[0][0] = (s1[0] == s2[0]);
  
  for (int i = 1; i < s1.size(); ++i) {
    partials[0][i] = max<int>(partials[0][i - 1], s1[i] == s2[0]);
  }
  
  for (int i = 1; i < s2.size(); ++i) {
    partials[i][0] = max<int>(partials[i - 1][0], s2[i] == s1[0]);
  }
  
  for (int i = 1; i < s2.size(); ++i) {
    for (int j = 1; j < s1.size(); ++j) {
      partials[i][j] = max<int>(max<int>(partials[i - 1][j],
                                         partials[i][j - 1]),
                                partials[i - 1][j - 1] + (s1[j] == s2[i]));
    }
  }
  
  // Produce string of longest common SS
  
  int i = s2.size() - 1;
  int j = s1.size() - 1;
  
  string longest;
  
  while (i >= 0 && j >= 0 && partials[i][j] > 0) {
    if (i > 0 && partials[i - 1][j] == partials[i][j]) {
      --i;
    }
    else if (j > 0 && partials[i][j - 1] == partials[i][j]) {
      --j;
    }
    else {
      longest += s2[i];
      --i;
      --j;
    }
  }
  
  reverse(longest.begin(), longest.end());
  
  return longest;
}

string shortestStringContainingSubsequences(const string& s1, const string& s2) {
  
  string longest = longestCommonSubsequence(s1, s2);
  string res;
  
  auto i = s1.begin();
  auto j = s2.begin();
  auto k = longest.begin();
  
  while (res.size() < s1.size() + s2.size() - longest.size()) {
    
    if (*j == *k) {
      
      // Append all chars in s1 not in s2 to result
      
      while (*i != *j) {
        res += *i;
        ++i;
      }
      
      ++i;
      ++k;
    }
    
    // Either append common char or char in s2 not in s1
    
    res += *j;
    ++j;
  }
  
  return res;
}

- DManchala16@students.claremontmckenna.edu September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this solution will work. Correct me if any test case would fail

public class Solution {
	
	
	public static void main(String[] args) {
		
		 System.out.println(findMinSubSequence("bfc", "bac"));
	}

	private static String findMinSubSequence(String string1, String string2) {
		
		HashMap<Character, Integer> hmap = new HashMap<Character, Integer>();
		StringBuilder sb = new StringBuilder();
		int len1 = string1.length();
		int len2 = string2.length();
		
		for(int i=0;i<len1;i++){
			Character c = Character.valueOf(string1.charAt(i));
			if(!hmap.containsKey(c)){
				hmap.put(c, Integer.valueOf(1));
			}else{
				hmap.put(c, hmap.get(c)+1);
			}
			sb.append(string1.charAt(i));
		}
		
		for(int i=0;i<len2;i++){
			Character c = Character.valueOf(string2.charAt(i));
			if(!hmap.containsKey(c)){
				sb.append(string2.charAt(i));
			}else{
				Integer val = hmap.get(c);
				if(val>0)
					hmap.put(c, hmap.get(c)-1);
				else
					sb.append(string2.charAt(i));
			}
		}
		
		return sb.toString();
	}

}

- Saravanan February 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findnumberofoccurancesinarray(char* arr, char c)
{
	int count=0;
	for (int i=0; i<strlen(arr); i++)
	{
		if (arr[i] == c)
		{
			count++;
		}
	}
	return count;
}

int maxchar( char* s1, char* s2, char c)
{
	int s1_Has = findnumberofoccurancesinarray(s1,c);
	int s2_Has = findnumberofoccurancesinarray(s2,c);
	if (s1_Has>s2_Has)
	{
		return s1_Has;
	}
	return s2_Has;
}

char* myconvert(char *s1, char *s2)
{
	int s1_len = strlen(s1);
	int s2_len = strlen(s2);

	char *result = new char[s1_len+s2_len];
	bool FoundInResult = false;

	for (int i=0; i< s1_len; i++)
	{
		for (int j=0; j<strlen(result);j++)
		{
			if (s1[i] == result[j])
			{
				FoundInResult = true;
				cout << "result ta bulundu: " << result[j] << endl;
				break;
			}
		}

		if (FoundInResult)
		{
			FoundInResult = false;
		}
		else
		{
			int maxnumber = maxchar(s1,s2, s1[i]);
			for (int j=0; j< maxnumber ; j++)
			{
				result[strlen(result)] = s1[i];
			}			
		}
	}
	
	for (int i=0; i< s2_len; i++)
	{
		for (int j=0; j<strlen(result);j++)
		{
			if (s2[i] == result[j])
			{
				FoundInResult = true;
				cout << "result ta bulundu: " << result[j] << endl;
				break;
			}
		}

		if (FoundInResult)
		{
			FoundInResult = false;
		}
		else
		{
			int maxnumber = maxchar(s1,s2, s2[i]);
			for (int j=0; j< maxnumber ; j++)
			{
				result[strlen(result)] = s2[i];
			}			
		}
	}

	return result;
}

- pclast December 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findnumberofoccurancesinarray(char* arr, char c)
{
	int count=0;
	for (int i=0; i<strlen(arr); i++)
	{
		if (arr[i] == c)
		{
			count++;
		}
	}
	return count;
}

int maxchar( char* s1, char* s2, char c)
{
	int s1_Has = findnumberofoccurancesinarray(s1,c);
	int s2_Has = findnumberofoccurancesinarray(s2,c);
	if (s1_Has>s2_Has)
	{
		return s1_Has;
	}
	return s2_Has;
}

char* myconvert(char *s1, char *s2)
{
	int s1_len = strlen(s1);
	int s2_len = strlen(s2);

	char *result = new char[s1_len+s2_len];
	bool FoundInResult = false;

	for (int i=0; i< s1_len; i++)
	{
		for (int j=0; j<strlen(result);j++)
		{
			if (s1[i] == result[j])
			{
				FoundInResult = true;
				cout << "result ta bulundu: " << result[j] << endl;
				break;
			}
		}

		if (FoundInResult)
		{
			FoundInResult = false;
		}
		else
		{
			int maxnumber = maxchar(s1,s2, s1[i]);
			for (int j=0; j< maxnumber ; j++)
			{
				result[strlen(result)] = s1[i];
			}			
		}
	}
	


	for (int i=0; i< s2_len; i++)
	{
		for (int j=0; j<strlen(result);j++)
		{
			if (s2[i] == result[j])
			{
				FoundInResult = true;
				cout << "result ta bulundu: " << result[j] << endl;
				break;
			}
		}

		if (FoundInResult)
		{
			FoundInResult = false;
		}
		else
		{
			int maxnumber = maxchar(s1,s2, s2[i]);
			for (int j=0; j< maxnumber ; j++)
			{
				result[strlen(result)] = s2[i];
			}			
		}
	}

	return result;

}

- pclast December 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is my solution

public class StringSubSequence {
    
    public static void main(String[] args) {
        System.out.println(findMinSubSequence("apple", "pear"));
    }
    
    public static String findMinSubSequence(String s1, String s2) {
        // check for any nulls
        if(s1 == null || s2 == null) {
            return "" + s1 + s2;
        }
        String tmp1 = stringSubSequence(s1, s2);
        String tmp2 = stringSubSequence(s2, s1);
        
        return tmp1.length() < tmp2.length() ? tmp1 : tmp2;
    }
    
    private static String stringSubSequence(String s1, String s2) {
        int index = 0;
        StringBuilder s3Result = new StringBuilder();
        for(char c : s1.toCharArray()) {
            s3Result.append(c);
            if(c == s2.charAt(index)) {
                index++;
            }
        }
        
        while(index < s2.length()) {
            s3Result.append(s2.charAt(index++));
        }
        
        return s3Result.toString();
    }
}

- AMP September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Greedy doesn't work.

S1=bfc
S2=bac

output of your program is
S3=bfcac

while the answer is
S3=bfac

- MehrdadAP September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Isn't this simple
Traverse first string. Take a pointer to second string. When char pointed in the second string equals current char in first string, increment pointer. do this until string one is fully traversed and pointer reaches string 2 end

- codealtecdown September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Greedy doesn't work.

I gave a counterexample to AMP's solution which is same as yours.

- MehrdadAP September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.


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