## Alcatel Lucent Interview Question for Developer Program Engineers

• 2

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.

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1

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

Comment hidden because of low score. Click to expand.
-2

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

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

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

}``````

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

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

}

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

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

Greedy doesn't work.

S1=bfc
S2=bac

S3=bfcac

S3=bfac

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

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

Greedy doesn't work.

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

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.

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.