## Deshaw Inc Interview Question for Financial Software Developers

• 1
of 1 vote

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

It is called the String Shuffle Problem,
And it is hard one, the brute force solution takes O(2^n) , and a dynamic programming solution takes O(n^2).

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

Here is the idea behind getting an algorithm in O(m+n), where m and n are the lengths of the two strings s1 and s2, such that s1+s2+s3, where + represents this strange concatenation.

Imagine a matrix with m columns and n rows. each column is labeled by a symbol in string s1, and each row is labeled by a character in string s2. If you draw it, look at where the vertical lines intersect the horizontal lines, and call these points. These intersections are the points of interest. The question becomes: if you start in the upper left point and you can only go right and down, can you reach the lower right corner? A move is valid only if the segment corresponding to the current character is the character in s3. If you start labeling the points with true if you can reach that point and with false otherwise (exploring false points is not interesting). First, label all the top points, then all the left points. Now start labeling the second row of points (left to right), then the next row, and so on.

If you can label the lower right point with true, them s1+s2=s3. Note that to actually find the correct interleaving, you need an auxiliary structure with back pointers.

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

``````bool f(char* s1, char* s2, char* s3)
{
if(*s1 == '\0' && *s2 == '\0' && *s3 == '\0')
{
return true;
}

if (*s3 == '\0')
{
return false;
}

if (*s1 == '\0' && *s2 == '\0')
{
return false;
}

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

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

lets say N=strlen(s1) + strlen(s2)

sort s3, and concat(s1,s2) ---- 2Nlog(N)
now compare(sorted s3, sorted concat(s1,s2)) --- N
(this step can be done in O(N) by keeping two iterators, one at the start and one at the end.)

So, the whole thing will be done in Nlog(N)

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

Not exactly. I suppose the order should be conserved as well

#include <iostream>

using namespace std;

int main(void)
{
char* str1 = "aabccabc";
char* str2 = "dbbabc";
char* str = "aabdbbccababcc";

int i, i1, i2;
i = i1 = i2 = 0;

int len = strlen(str);
int len1 = strlen(str1);
int len2 = strlen(str2);

int clen = 0;

for (int i = 0; i < len; ++ i) {

cout << i << " " << i1 << " " << i2 << " " << clen << endl;

// state 0: can't determine which str to match
if (str[i] == str2[i2] && str[i] == str1[i1]) {
++ clen;
++ i2;
++ i1;
}
// state 1.1: next str1 character matches, reset the common length value
else if (str[i] == str1[i1]) {
i2 -= clen;
clen = 0;
++ i1;
}
// state 1.2: next str2 character matches, reset the common length value
else if (str[i] == str2[i2]) {
i1 -= clen;
clen = 0;
++ i2;
}
// state 2.1: previous str2 character matches, advance i2
else if (str[i] == str2[i2 - clen]) {
i2 = i2 - clen + 1;
clen = 0;
}
// state 2.2: previous str1 character matches, advance i1
else if (str[i] == str1[i1 - clen]) {
i1 = i1 - clen + 1;
clen = 0;
}
else {
cout << "false at " << i << " " << i1 << " " << i2 << endl;
return 1;
}

}

cout << "true" << endl;

return 0;
}

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

I think the solution to this problem is very simple.

Mantain 3 pointers

1. Point the first pointer to str3.second pointer to s1 and third pointer to s2.

2.Keep on incrementing str3 pointer.For each value,check whether the value at pointer is similar to str1 pointer or similar to str2.
if similar increment that pointer.
If not return false.

3.If at any point we encounter null at str1 pointer or str2 pointer,simply compare strcmp(str3 pointer,str1 or str2 pointer)

Complexity is O(1).

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

wot if the ptr value is similar to both....

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

How it could be o(1);
U r comparing each character in str3;
So Ur algo depends on number of chars in str3;
So it must be having complexity O(n)

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

This solution has a slight problem. A simple counter example to it is, consider the strings:
str1 = abc
str2 = akc
str3 = akabcc

The answer to it is clearly true, since str1 and str2 can be interleaved to get str3.
But with your approach, str3 will match with str1, and you would increment the pointers for str1 and str3, and then it would return false which is wrong.

To correct this, one needs to somehow handle the case when the pointers of str1 and str2 both point to the same values and it matches with the value pointed by str3 pointer. This can be done by making recursive calls to both the cases.

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

if both the pointr values are same then proceed with checking the next character.. till u find a character which is common in only one string pointer.

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

what if you cannot find?
s1=abcab
s2=abdab
s3=ababcdabab

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

wat if we use count sort principle...i.e. determine freq of each char in s1 increase freq count as u run thru it den do d same for s2 and increase freq count in d same array...so d extra aaray used now contains addition of freqs of chars frm s1 and s2..now run thru s3 and as u run decrement the counts.....after u r done run thru the extra array that holds freq and at no point shd u get freq < 0

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

Vanda is right

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

Here is a recursive solution:-

bool does_interleave(string w1, string w2, string w3)
{
....size_t l1 = w1.size();
....size_t l2 = w2.size();
....size_t l3 = w3.size();

....if (l3 == 0 && (l1 != 0 || l2 != 0)) return false;

....if ((l1 == 0 && w2 == w3) || (l2 == 0 && w1 == w3)) {
........return true;
....} else {
........bool ret = false;
........if (w1[l1-1] == w3[l3-1]) ret = does_interleave(w1.substr(0,l1-1), w2, w3.substr(0, l3-1));
........if (!ret && w2[l2-1] == w3[l3-1]) ret = does_interleave(w1, w2.substr(0,l2-1), w3.substr(0, l3-1));
........return ret;
....}
}

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

Missing the look up.
Lookup the the biggest common ahead, and chek next diff char to decide one string to match.

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

@Vanda..
I think there is a flaw in your algo:-

say if word1 = abdg, word2 = dgc , word3 = abdgcdg
if i am not wrong, your algo wud successfully compare till
word1 = null and word = dgc and word3 = cdg. Then compare dgc and cdg and return false. But this case is actually a "TRUE" return case.
ab"dgc"dg

Think over...

Thanks,
Rohith Menon.

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

won't looking for looking for longest match solve this problem?

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

guys, let's consider the following fact:
I keep countArr and initialize it with all '0' now parse down
all s1 and s2 and increment count in countArr. like countArr[s1[i]]++
now parse down s3 and decrement countArr[s3[i]]--;
after this, if all items of countArr are not 0 then s3 can't be formed with s1 and s2.
However even if it is 0 then it does not imply s3 can be formed. The
condition I have checked in necessary but not sufficient :( because
if s3 is taken out in random order from s1 and s2 then also the above
condition will be satisfied, but s3 will not be the desired one!

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

arnab your algorithm will work with a minor change. you can initialize the array with data from S3 first and then use S1 and S2 to decrement the counters. If at the end the entire array has 0's, then you got your answer.

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

Ikonos / Arnab ,
How will you ensure the order ?

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

The idea from Vandna is something that strikes my mind after reading the question. Vandna's approach is correct provided we never end up in a situation where we've a particular character that appears in both of the strings and we're stuck as to which one is the correct one.

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

how about to check whether the given sequence is a subsequence of the concatenated string of s1 and s2 , i guess this sure will solve the problem

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

how about to check whether the given sequence is a subsequence of the concatenated string of s1 and s2 , i guess this sure will solve the problem

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

not possible wrong idea

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

Here is the idea behind getting an algorithm in O(m+n), where m and n are the lengths of the two strings s1 and s2, such that s1+s2+s3, where + represents this strange concatenation.

Imagine a matrix with m columns and n rows. each column is labeled by a symbol in string s1, and each row is labeled by a character in string s2. If you draw it, look at where the vertical lines intersect the horizontal lines, and call these points. These intersections are the points of interest. The question becomes: if you start in the upper left point and you can only go right and down, can you reach the lower right corner? A move is valid only if the segment corresponding to the current character is the character in s3. If you start labeling the points with true if you can reach that point and with false otherwise (exploring false points is not interesting). First, label all the top points, then all the left points. Now start labeling the second row of points (left to right), then the next row, and so on.

If you can label the lower right point with true, them s1+s2=s3. Note that to actually find the correct interleaving, you need an auxiliary structure with back pointers.

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

Here is the idea behind getting an algorithm in O(m+n), where m and n are the lengths of the two strings s1 and s2, such that s1+s2+s3, where + represents this strange concatenation.

Imagine a matrix with m columns and n rows. each column is labeled by a symbol in string s1, and each row is labeled by a character in string s2. If you draw it, look at where the vertical lines intersect the horizontal lines, and call these points. These intersections are the points of interest. The question becomes: if you start in the upper left point and you can only go right and down, can you reach the lower right corner? A move is valid only if the segment corresponding to the current character is the character in s3. If you start labeling the points with true if you can reach that point and with false otherwise (exploring false points is not interesting). First, label all the top points, then all the left points. Now start labeling the second row of points (left to right), then the next row, and so on.

If you can label the lower right point with true, them s1+s2=s3. Note that to actually find the correct interleaving, you need an auxiliary structure with back pointers.

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

Hi... Please explain your logic with the support of an example.. It is not clear!!

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

Hi... Please explain your logic with the support of an example.. It is not clear!!

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

Hi Stefan,

Please explain it with the help of an example.. As it is not clear!!

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

``````int p1,p2,p3
int c1[],c2[],c3[], cp;

p1=p2=p3=0;
cp=0;

while(true)
{
if(s3[p3]=='\0')
{
if(s2[p2]!='\0' || s1[p1]!='\0')
{
if(cp>0)
{
//backtrack
p1=c1[cp-1];
p2=c2[cp-1];
p3=c3[cp-1];
cp--;
p3++;
p2++;
}
else
{
return false;
}
}
}

if(s3[p3]==s1[p1] && s3[p3]!=s2[p2])
{
p3++;
p1++;
}
else if(s3[p3]==s2[p2] && s3[p3]!=s1[p1])
{
p1++;
p3++;
}
else if(s3[p3]==s1[p1] && s3[p3]==s2[p2])
{
c1[cp]=p1;
c2[cp]=p2;
c3[cp]=p3;
p1++;
p3++;
cp++;
}
else
{
if(cp>0)
{
//backtrack
p1=c1[cp-1];
p2=c2[cp-1];
p3=c3[cp-1];
cp--;
p3++;
p2++;
}
else
{
return false;
}
}
}``````

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

``````How about the following approach?

if ( len(s3) != len(s1) + len(s2))
return FALSE;
if(LCS(s1,s3) != s1)
return FALSE;
if(LCS(s2,s3) != s2)
return FALSE;

return TRUE;``````

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

``````BOOL
IsInterleave(char *S1,char *S2,char *S3)
{
BOOL Ret;

printf("S1 = %s,S2 = %s, S3 = %s\n",S1,S2,S3);

if(*S1 == '\0' && *S2=='\0' && *S3== '\0')
return TRUE;

if(*S1 == *S3)
{
Ret = IsInterleave(++S1,S2,++S3);
if(Ret)
return TRUE;
}
if(*S2 == *S3)
{
Ret = IsInterleave(S1,++S2,++S3);
if(Ret)
return TRUE;
}
return FALSE;
}``````

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

counting sort variation is best for such cases .... if space is not the issue....

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

This code 'll work for all the cases:

``````#include<iostream>
using namespace std;
bool compare(char *s1, char *s2, char *s3)
{
bool x=false,y=false;
if(!*s1 && !*s2 && !*s3)
{
return true;
}
if((*s1 || *s2) && !*s3)
{
return false;

}
if(*s1)
{
if(*s1 == *s3)
{
s1++;
s3++;
x = compare(s1,s2,s3);
}
}
if(*s2)
{
if(*s2 == *s3)
{
s2++;
s3++;
y  = compare(s1,s2,s3);
}
}
//cout<<x<<"  "<<y<<endl;
if(x || y)
{
return true;
}
else
{
return false;
}

}
int main()
{
char str1[] = "abcab";
char str2[] = "abdab";
char str3[] = "ababcdabab";
bool find = compare(str1,str2,str3);
if(find)
{
cout<<"Interleaving is done.\n";
}
else
cout<<"Interleaving is not done\n";
return 0;
}``````

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

it is a simple problem and can be done in O(m*n) where m and n arre size of string s1 and string s2 respectively.

here's hint
use longest common subsequence algorithm (dynamic programming) on s1 and s3 mark characters in s3 which are matched with s1. now remaing string of s3 can be compared to s2 if they are same then accept else reject. (O(n) +O(m*n))

let me know if I am wrong...

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

``````def is_interleaved(string, s1, s2):

if len(string) != len(s1) + len(s2):
# No way we can be interleaved
return False

if string == s1 + s2 or string == s2 + s1:
# Will capture case where string is one or two letters
return True

letter = string
letter_1 = s1 if len(s1) > 0 else ""
letter_2 = s2 if len(s2) > 0 else ""

result_1 = False
result_2 = False
if letter == letter_1:
result_1 = is_interleaved(string[1:], s1[1:], s2)
if letter == letter_2:
result_2 = is_interleaved(string[1:], s1, s2[1:])
return result_1 or result_2``````

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

Code form of Stefan algorithm
///
public static boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0) {
return true;
} else if (s3.length() != s1.length() + s2.length()) {
return false;
}
boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];

for (int s1Index = 0; s1Index <= s1.length(); ++s1Index) {
for (int s2Index = 0; s2Index <= s2.length(); ++s2Index) {
isInter[s1Index][s2Index] = (s1Index == 0 && s2Index == 0)
|| (s1Index > 0 && s1.charAt(s1Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index-1][s2Index])
|| (s2Index > 0 && s2.charAt(s2Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index][s2Index-1]);
}
}
return isInter[s1.length()][s2.length()];
} \\\

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

Code form of Stefan algorithm

``````public static boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0) {
return true;
} else if (s3.length() != s1.length() + s2.length()) {
return false;
}
boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];

for (int s1Index = 0; s1Index <= s1.length(); ++s1Index) {
for (int s2Index = 0; s2Index <= s2.length(); ++s2Index) {
isInter[s1Index][s2Index] = (s1Index == 0 && s2Index == 0)
|| (s1Index > 0 && s1.charAt(s1Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index-1][s2Index])
|| (s2Index > 0 && s2.charAt(s2Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index][s2Index-1]);
}
}
return isInter[s1.length()][s2.length()];
}``````

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.