## Interview Question

• 0

Given three strings , find how many ways can the third string be generated by combining susequences of first and second strings in any order.
combining eg:“abc” and “de” can yield adebc,abdce,abcde etc...

Country: India
Interview Type: In-Person

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

Hey folks. This is not strict permutation or combination problem as suggested
by some guys above. This is a classic proper shuffling problem, when you have to
shuffle two sets while maintaining their relative order (e.g. a1 a2 a3 shuffled
with b1 b2 b3 b4 => b1 a1 a2 b2 a3 b3 b4).
This can be easily solved recursively using the following algorithm:
Suppose we have two strings to shuffle: "abc" and "de"
1. take the second string "de"
2. for each char of the string "de", insert it into every possible positions in the string "abc"
e.g. d + "abc" => [dabc; adbc; abdc; abcd;] (1)
3. Now, insert all the following chars of the string "de", in this case only the "e",
into all the possible positions in the strings (1), while noting that in each
case the letter "e" should succeed the letter "d".

For our example (the strings "abc" and "de") it will result in:

``````add "d" to every possible positions of "abc"

dabc         (tmp1)
abdc         (tmp3)
abcd         (tmp4)

add the "e" to every possible position after letter "d" in the strings tmp1-tmp4

for "dabc"
deabc   (s1)
daebc   (s2)
dabec   (s3)
dabce   (s4)

for "abdc"
abdec   (s8)
abdce   (s9)

for "abcd"
abcde   (s10)``````

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

so to check for the third string, we have to generate all correct shuffles and check with the third string? Can we use dynamic programming?

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

You do not need to check for the third string, just generate the proper shuffle series as described in the above algorithm. As for DP, I do not think this is required here, because we do not need to store any intermediate values to help us eliminate any recomputing - just a simple recursive algorithm is fine here, something similar to what shondik's code snippet does.

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

But the question asks to find the no of ways the third string can be generated using the first two!!

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

@marti
In "find the no of ways the third string can be generated" could you please specify what is meant by "the third string" then? I think the problem statement is defined somewhat bad. In suggesting the algorithm, I presumed that the problem is like: "Given two strings find all the proper shuffles of those strings". If this is not what the problem poster had in mind, then I think the problem needs to be re-worded to make it unambigous and clearly defined.

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

3 strings are given, we need to find no. of ways to make 3rd from first two using given rules

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

This is basically a backtracking algorith.

``````void print(char *s1,char *s2,char *s3,int N1,int N2,int depth)
{
int i;
if(N1==0 && N2==0)
{
for(i=0;i<depth;i++)
printf("%c",s3[i]);
printf("\n");
}
if(N1!=0)
{
s3[depth]=*s1;
print(s1+1,s2,s3,N1-1,N2,depth+1);
}

if(N2!=0)
{
s3[depth]=*s2;
print(s1,s2+1,s3,N1,N2-1,depth+1);
}
}

int main()
{
char s1[]="abc",s2[]="de",s3[10];

print(s1,s2,s3,strlen(s1),strlen(s2),0);
return 0;
}``````

The explanation goes as follows:
1. First include the first character of string 1 & iterate for the rest of take of the characters.
2. Apply the same for the second string.
3. If both the strings are finished, output string 3.

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

@shondik
Though the implementation works properly, I wouldn't call it a "backtracking algorithm", because you do not discard any intermediate solutions based on some criteria. Instead, you incrementally build the solution.

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

it is 10

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

for abc, there are 2^3=8 substrings
for de, there are 2^2=4 substrings
there are 2 ways to combine two substrings,
therefore, there are 8*4*2=64 combinations

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

in general, for string A with length m and B with length n
2*(2^m)*(2^n)=2^(n+m+1)

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

Isn't this same as finding anagrams of a given word?

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

Solution= Factorial(str1.length + str2.length + ... + strN.length);
Solution = solution/Factorials of no of repeating characters for each character;

Example,
For above example of abc, abc, abc, sol = fac(9)/(fac(3)*fac(3)*fac(3)); because a, b and c each repeat 3 times. Thats it!!

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

BTW I am assuming that when marti says "in any order", you can really permute. Otherwise, my solution wont hold.

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

no, its not the same,Eg: for
stirng1: abc
string 2:abc
string 3:abc

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

should be 5! = 120

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

Yeah as we can sum up the total length and applying permutations and combinations we have the possible ways of arranging the letters of the string. Which is nothing but the factorial.

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

This is NOT correct. That way we will have a string like " edcba" which is NOT correct as "cba" is NOT subsequence of "abc"

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

I think the answer should be 5!/(3!*2!) then the relative order of both strings is maitained

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

DP solution, the boundary is important.

``````#include <iostream>
using namespace std;

int num[50][50];

int main() {
string a = "decba", b = "cba", c = "deccbaba";
num[0][0] = 1;
for(int i = 0; i <= a.length(); i++) {
for(int j = 0; j <= b.length(); j++) {
if (i == 0 && j != 0 && b[j-1] == c[i+j-1]) {
num[i][j] = num[i][j-1];
} else if (i != 0 && j == 0 && a[i-1] == c[i+j-1]) {
num[i][j] = num[i-1][j];
}
if (i == 0 || j ==0) {
continue;
}
if(a[i-1] != b[j-1]) {
if(a[i-1] == c[i+j-1]) {
num[i][j] = num[i-1][j];
} else if (b[j-1] == c[i+j-1]) {
num[i][j] = num[i][j-1];
} else {
num[i][j] = 0;
}
} else {
if (a[i-1] == c[i+j-1]) {
num[i][j] = num[i][j-1] + num[i-1][j];
} else {
num[i][j] = 0;
}
}
}
}
cout << "Number of methods is " << num[a.length()][b.length()] << endl;
return 0;
}``````

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

Can you explain in words please?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### 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.