Amazon Interview Question
Software Engineer / DevelopersProblem :
----------
Return the common string from 2 strings of arrays in optimal running time.
Example/Algo:
------------
S1{tarun}
S2{Varun}
R{arun}
Key Solution :
--------------
Compare the S1 1st char with S2 1st char
if not match then increment J
and continue matching till match is found.
Once match is found increment i & j till i!=j then break.
Code:
---------
Private string Returncommonstrg(String S1 , String S2)
{
For (int i=0 ; i<N-1 ; i++)
{
For (int j=0 ; J<N-1 ; J++)
{
char ch1 = S1[i];
char ch2 = S2[j];
if (Ch1==Ch2)
{
string result += S1[i];
i++;
}
}
}
Return result;
}
Order:
---------
O(N^2)
You can build a suffix tree of both strings in O(N) and doing a depth first search, you can find the answer.
- Bala February 27, 2010