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.
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
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