Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
Solution:
bool test(A,B,C)
{
i=j=k=0;
while(k < C.size())
{
if(i < A.size() && C[k]==A[i])
{i++,k++;
}
else if(j < B.size() && C[k]==B[j])
{
j++,k++;
}
else
return false
}
return (i == A.size() && j == B.size());
}The above algorithm doesn’t work when C[k]=A[i]=B[j], essentially throwing one in to a dilemma whether to accept the character from A or B.
- Find the intersection of these arrays A and B.
Solution:The intersection can be found by using a variation of merge routine of the merge sort.
- If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?
Solution:In this case for each entry of smaller array,we can run a binary search routine on the larger one to know its presence.
Tags: google, Interview, Question
