Interview Question
Country: India
Interview Type: In-Person
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)
adbc (tmp2)
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 "adbc"
adebc (s5)
adbec (s6)
adbce (s7)
for "abdc"
abdec (s8)
abdce (s9)
for "abcd"
abcde (s10)
Adding the link to my solution of the problem:
codepad.org/gT4EdzdG
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?
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.
But the question asks to find the no of ways the third string can be generated using the first two!!
@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.
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.
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
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!!
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.
This is NOT correct. That way we will have a string like " edcba" which is NOT correct as "cba" is NOT subsequence of "abc"
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;
}
no, its not the same,Eg: for
- marti June 22, 2012stirng1: abc
string 2:abc
string 3:abc
answer is 8