Yahoo Interview Question for Software Engineer / Developers






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

if the elements are different it can be done in O(n+m). Otherwise it would be O(n^2) using dynamic programming.

bool func(int i1=0,int i2=0,int i3=0)
    if(i3==C.size()) return 1;
    if(dp[i1][i2]!=-1) return dp[i1][i2];
    if(i1<A.size() && C[i3]==A[i1])
          x=func(i1+1,i2,i3+1);
     if(i2<B.size() && C[i3]==A[i2])
          x=x|func(i1,i2+1,i3+1);
    return dp[i1][i2]=x;

I would like you to observe that to define the state in dynamic programming(in this case) by just i1,i2. i3 is not required for memoization since always i3=i1+i2;
Since there are n^2 states and each state takes O(1) time the overall time complexity will be O(n^2)

- Anonymous September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort C.
Sort A and B. Merge sort can be used and concatenate these two sorted lists. Check if they are equal( C ?= A+B(merged) ). If yes then answer is YES.

- cac September 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

umm..just struck me - why do we need to get into dp? Will this work (a very simple algo)

first check length of bigger string = len(s1) + len(s2)
pick up the first string and look for its letters (in the same order) in the bigger string - if all the letters are consumed, proceed - replace the letters thus consumed with say a space
now for the remaining letters check if the letters of the second string are consumed, => if yes, true

even in case of repition, it should work because the order would be preserved regardless of whether the letter was taken from 1st string or 2nd.

consider -

s1 - abcd
s2 - bccld

abbccdcld

checking for letters of s1:

the frst a,b,c,d crossed out
=> __b_c_cld

checking for the letters of 2nd string => consumed - yes! :D

O(n + m)

- RB October 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

{{
can you explain how the order would be O(m+n)

because I think for canceling out the elements from bigger string you have to search the smaller string whether the current character is in the string or not.
}}

- Aditya October 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah i agree with aditya..the complexiety will not be o(m+n).it wud be 0((m+n)2)..

- dinesh March 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh I don't think that would be necessary, mate!
See...you need not search the whole string if you don't find a letter. you will be searching for the first small string in the large string. And in case you don't find a character of the smaller string in the larger one, going ahead, you stop there and say "It ain't an interleaving".
Say, if the big string above was abbkkdkld, you would find a, then b, and then you won't find c of the str1 after ab.... That's it. you stop there...

- prakhargahlot July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How will it work for: aba, bca, and abcaba?
As you can see, the third string is valid. But, based on your approach, after the first step, the string will be __c_ba and your algo will return false.

- Anonymous October 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

if string comprised of ASCII characters only then

first check strlen(C) == strlen(A) + strlen(B)


make an array F[256]
initialize all Elements of F with 0.
then scan string A and for i=0 to strlen(A) do F[A[i]]++
then scan string B and for i=0 to strlen(B) do F[B[i]]++
then scan string C and for i=0 to strlen(C) do F[C[i]]--

then check whether all elements are zero or not !! DONE

- Aditya October 11, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

String 1:abcd
String 2:efgh
String 3: cdabghef

Your algorithm fails in this case.. Didn't take the order of string into account.

- Delon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Return true only if all the following conditions are satisfied
1) LCS of A and C should be equal to length of A
2) LCS of B and C should be equal to length of B
3) length(A) + length(B) = length(C)

- Rama B October 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess there exists a pretty simple linear complexity solution.

Take 3 variables to store indexes of strings a,b,c
Iterate all chars of c using cindex. If char matches current char frm a, move a and c indeces
If char matches current char from b, move b and c indexes
However if char doesn't match any of cur a,b current chars then c isn't interleaved

However if all chars of c were matched with some a,b char then c is interleaved

- Hjindal January 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we reduce this to the problem of finding whether two strings are anagrams or not?

1.concatenate A and B into T.
2. Sort T using count sort - O(256 + strlen(T))
3. Sort C using count sort - O(256 + strlen(C))
4. Check if T and C are the same - O(strlen(T) + strlen(C))

- Anonymous April 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// helper : is A a subsequence of C
bool isSubsequence(char *a, char *c){
 int i=0,j=0;
   while(a[j] && c[i]){
      if(a[j] == c[i]) { j++;}
      i++;
   }
   if(a[j]) return false;
}

bool isInterleaved(char *a, char *b, char *c){

     return isSubsequence(a,c) && isSubsequence(b,c) && (strlen(a)+strlen(b)==strlen(c));
}

- Anonymous February 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// helper : is A a subsequence of C
bool isSubsequence(char *a, char *c){
   int i=0,j=0;
   while(a[j] && c[i]){
      if(a[j] == c[i]) { j++;}
      i++;
   }
   return a[j] ? false : true;
}

bool isInterleaved(char *a, char *b, char *c){

     return isSubsequence(a,c) && isSubsequence(b,c) && (strlen(a)+strlen(b)==strlen(c));
}

- monkeyyy February 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if
a = "aab"
b = "aab"
c = "aaabaa"

your solution will give true.

- Anonymous February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ monkeyyy
what if
a = "aab"
b = "aab"
c = "aaabaa"

your solution will give true.

- Anonymous February 18, 2012 | Flag Reply


Add a Comment
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.

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