Alcatel Lucent Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
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);}}
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;
}
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();
}
}
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;
}
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;
}
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();
}
}
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
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.
- MehrdadAP September 03, 2015