Google interview : Interleaved string
Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
int isInterleaved(char* str1,char* str2,char* str3)
ReplyDelete{
int alphabets[26]={0};
int len1=strlen(str1);
int len2=strlen(str2);
for(int i=0;i<len1;i++)
{
alphabets[str1[i]-'a']++;
}
for(int i=0;i<len2;i++)
{
alphabets[str2[i]-'a']++;
}
for(int i=0;i<strlen(str3);i++)
{
alphabets[str3[i]-'a']--;
}
for(int i=0;i<26;i++)
{
if(alphabets[i]!=0)return 0;
}
return 1;
}
@ankit your approach is good but try finding out some pattern,to do it without using extra space...
ReplyDeletealgo :
ReplyDeletexnor(C,A+B)
this function will return the number of similiar characters(say static sim, increment sim if similar character is found in the pattern) in C and A+B,right Shift A+B by one and continue till the length of C, (you can call xnor recursively) , then do the same by taking the A+B to the ptr+(length(C)-lenght(A+B))and left shifting by one continue till the length of C, (you can call xnor recursively)..
in the calling programm if sim == length(A+B) => Yes interleaved, other wise no.
one question is C's length = lengh (A+B) or it can have other characters as well??
@softy32 in case c has any other character then it is not interleaved...
ReplyDeletehmmm ok thn wt r ur comments for my logic..!!
ReplyDelete