Synopsys R&D Interview Question
Senior Software Development EngineersCountry: India
Ex: String2 = "ABC"; String1="AXBYCZ". Answer = true;
Simple Algo:
First look for 1st char, then 2nd char in remaining string and so on..
boolean f(String str1, String str2)
{
int begIndex = 0;
for(int i=0; i<str2.length; ++i){
int pos = str1.indexOf(str2.charAt(i), begIndex);
if(pos == -1) return false;
begIndex = pos+1;
}
return true;
}
Need more details in problem def, for more sophisticated solution.
I think your interpretation of the problem makes more sense than the other ones. One tiny issue, I think it should be "begIndex = pos+1" so that if String2 = "ABCC" then Answer = false.
1.) Put all characters string2 in a stack.
2.) Then start traversing string1 in reverse order
2.1) If currect character matches with top of stack then pop it from stack.
3.) After traversing string1 fully, If stack is empty then return true else return false
Why use extra stack space and put all the chars of string2 on to it? Why traverse from the end of string1? Why this additional complexity? Is it in anyway more efficient than starting from the beginning of both the strings and comparing them character by character?
- Anonymous June 27, 2013