## Interview Question

Country: United States

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

Construct a (n1+1)*(n2+1) table, A[0 .. n1][0 .. n2], where n1 and n2 is the length of s1 and s2, respectively.
A[i][j] = true, i.e. s3[0 .. i+j-1] is an interleaving of s1[0 .. i-1] and s2[0 .. j-1].
Thus, A[n1][n2] represents whether s3 is a interleaving of s1 and s2.
To build up such a table,
1.Set A = true. Period.
2.Initialize the first row. The first row means whether s1[0 .. (n1-1)] matches s3[0 .. (n1-1)], correspondingly.
3.Similarly, initialize the first column which means whether s2[0 .. (n2-1)] matches s3[0 .. (n2-1)], correspondingly.
Now we fill up the table. For A[i][j], s3[0 .. (i+j-1)] match? s1[0 .. i-1] weaving s2[0 .. j-1]
4.Note that A[i-1][j] comes from s1[0 .. i-2] weaving s2[0 .. j-1]. Thus, if it is true, we need to compare s1[i-1] with s3[i+j-1].
Similarly, A[i][j-1] comes from s1[0 .. i-1] weaving s2[0 .. j-2]. Thus, if it is true, compare s2[j-1] with s3[i+j-1].

5.Return A[n1][n2]

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

If I have to do this exercise once, I would just do a linear walk through the characters and find the answer like below.

``````Assume sizea, sizeb sizec are the respective array sizes.

// NOTE: watch out for the \0 at the end.
if ((sizea != sizeb) || ((sizec-1) != (sizea-1+sizeb-1))) {	// -1 => take out \0 at the end.
printf("Perfect interleaving not possible.\n");
return -1;
}

ptrA = a; 	ptrB = b; 	ptrC = c;
sizea -= 1;	// cut off the \0 char

while (sizea) {
if (*ptrA++ != *ptrC++) {
break;
}

if (*ptrB++ != *ptrC++) {
break;
}

sizea--;
}

if (sizea == 0) {
printf("Perfect interleave.\n");
} else {
printf("No interleave.\n");
}``````

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

u see your code only does a trivial check it will fail for many test cases

for eg:- let's say A="AAA" and B="AAB" and interlevead string be C="AABAAA"

if (*ptrA++ != *ptrC++) {
break;
}
will give true for first 2 A's but after that your logic will fail as C will now point to "B" A is pointing to 'A' and B is also pointing to "A"..And you will come out of the loop.

because of these test cases you need to come with a dynamic programming.
Which is there in my post below you.

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

``````public static boolean isInterleavingString(String s1, String s2, String s3) {
int p1 = 0;
int p2 = 0;
int prevStr = 0;
for (int i = 0; i < s3.length(); i++) {

if (prevStr == 0) {
if (p1 < s1.length() && s3.charAt(i) == s1.charAt(p1)) {
p1++;
} else if (p2 < s2.length() && s3.charAt(i) == s2.charAt(p2)) {
p2++;
prevStr = 1;
} else {
return false;
}
} else {
if (p2 < s2.length() && s3.charAt(i) == s2.charAt(p2)) {
p2++;
} else if (p1 < s1.length() && s3.charAt(i) == s1.charAt(p1)) {
p1++;
prevStr = 0;
} else {
return false;
}
}
}
return p1 == s1.length() && p2 == s2.length();
}``````

Test Cases:

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

can handle duplicates, with DP

``````public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length()) return false;
int[][] dp = new int[s1.length()+1][s2.length()+1];
return isInterleave(s1,s2,0,0,s3,dp);
}

private boolean isInterleave(String s1, String s2, int i1, int i2, String s3, int[][] dp) {
if (i1 == s1.length() && i2 == s2.length()) return true;
if (dp[i1][i2] > 0) return dp[i1][i2] == 2;
boolean result = false;
if (i1 == s1.length()) result = s2.charAt(i2) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1,i2+1,s3,dp);
else if (i2 == s2.length()) result = s1.charAt(i1) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1+1,i2,s3,dp);
else if (s1.charAt(i1) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1+1,i2,s3,dp)) result = true;
else if (s2.charAt(i2) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1,i2+1,s3,dp)) result = true;
dp[i1][i2] = result ? 2 : 1;
return result;
}``````

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

``````bool match(const char* s1, const char* s2, const char* s3)
{
if (*s3 == '\0')
return *s1 == '\0' && *s2 == '\0';

return (*s1 == *s3) && match(s1 + 1, s2, s3 + 1) ||
(*s2 == *s3) && match(s1, s2 + 1, s3 + 1);
}``````

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

Java DP solution

``````public boolean isInterleave(String s1, String s2, String s3) {
if ( (s1.length()+s2.length()) != s3.length() ) return false;
boolean[][] DP= new boolean[s1.length()+1][s2.length()+1];
//base case: an empty string is always the interleave of two other empty string
for (int p1 = 0; p1 <= s1.length(); p1++) {
for (int p2 = 0; p2 <= s2.length(); p2++) {
DP[p1][p2] = ( p1==0 && p2==0 ) //Base case of 2 empty strings
|| ( p1 > 0 && DP[p1-1][p2] && s1.charAt(p1-1)==s3.charAt(p1+p2-1) )
|| ( p2 > 0 && DP[p1][p2-1] && s2.charAt(p2-1)==s3.charAt(p1+p2-1) );
}
}
return DP[s1.length()][s2.length()];
}``````

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

Whoever vote me down, could you tell me what's wrong with my code?

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.