Interview Question

  • -
    0
    of 0 votes
    21
    Answers

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

    - marti on June 22, 2012 in India Report Duplicate | Flag
    Algorithm

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

- ashot madatyan on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- marti on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ashot madatyan on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- marti on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ashot madatyan on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- marti on June 28, 2012 | Flag
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.

- Aashish on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ashot madatyan on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is 10

- wyb2012 on June 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- wyb2012 on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Sandeep on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!!

- axecapone on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- axecapone on June 22, 2012 | Flag
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
answer is 8

- marti on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

should be 5! = 120

- Anonymous on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- pulkit on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- loveCoding on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- siva on June 22, 2012 | Flag
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;
}

- poxzlm on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain in words please?

- marti on June 22, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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