Deshaw Inc Interview Question
Software Engineer / DevelopersIt's easy to just say "Suffix tree", O(n), etc. bla-bla-bla. Could you please wirte WORKING solution using Suffix tree ? And please think that you have to do it during interview in 10-15 minutes...
std::string largestPalindrome(const std::string& in)
{
using namespace std;
//every element contains length of palindrome
// ending at this index
vector<int> a;
a.resize(in.size());
std::fill(a.begin(), a.end(), 1);
if(in[0] == in[1])
a[1] = 2;
//initialized to 1
for(int i=2; i < a.size();i++)
{
if(in[i]==in[i-1])
a[i]=2;
if(in[i]==in[i-2])
a[i]=3;
if(i-a[i-1]-1 >=0)
if(in[i]==in[i-a[i-1]-1])
a[i]=a[i-1]+2;
}
int pos = 0, max = 0;
for(int i = 0; i < a.size(); ++i )
{
if( a[i] > max )
{
max = a[i];
pos = i;
}
}
if( max > 1 )
{
return in.substr(pos-max+1, max);
}
return "";
}
/// finds largest palindrome which occures in given string
std::string largestPalindrome(const std::string& in)
{
using namespace std;
//every element contains length of palindrome
// ending at this index
vector<int> a;
a.resize(in.size());
std::fill(a.begin(), a.end(), 1);
if(in[0] == in[1])
a[1] = 2;
//initialized to 1
for(int i=2; i < a.size();i++)
{
if(in[i]==in[i-1])
a[i]=2;
if(in[i]==in[i-2])
a[i]=3;
if(i-a[i-1]-1 >=0)
if(in[i]==in[i-a[i-1]-1])
a[i]=a[i-1]+2;
}
int pos = 0, max = 0;
for(int i = 0; i < a.size(); ++i )
{
if( a[i] > max )
{
max = a[i];
pos = i;
}
}
if( max > 1 )
{
return in.substr(pos-max+1, max);
}
return "";
}
<pre lang="java" line="1" title="CodeMonkey86418" class="run-this">class LongestPalindrom {
public static void main(String args[]){
String str = "exaaxamsimpleelpmisle";
char[] a = str.toCharArray();
int low=Integer.MAX_VALUE;
int upper=Integer.MIN_VALUE;
for(int i=0;i<str.length();i++){
int start=i;
int end =i;
while(start>=0 && end < str.length()){
if(a[start]==a[end]){
if(end-start>upper-low){
upper=end;
low=start;
}
end++;
start--;
}else{
break;
}
}
}
for(int i=0;i<str.length();i++){
int start=i;
int end =i+1;
while(start>=0 && end < str.length()){
if(a[start]==a[end]){
if(end-start>upper-low){
upper=end;
low=start;
}
end++;
start--;
}else{
break;
}
}
}
for(int i=low;i<=upper;i++){
System.out.print(a[i]);
}
}
}
</pre><pre title="CodeMonkey86418" input="yes">1
2
10
42
11
</pre>
LongestPalindrome(char[] input, int len)
{
Int left, right, l, r;
Left = right =l = r = -1;
If(l<2) return;
For(int i=1; i<n;n++)
{
If (input[i] == input[i-1])
{
L = i-1; r=I;
}
Else if(input[i] == input[i-2])
{
l=i-2; r=I;
}
If (l!=-1)
{
While (l >=0 && r <n && a[l]==a[r])
{
l--; r++;
}
}
l++; r--;
If (r-l > right-left)
{
right = r;
left = l;
}
L = r = -1;
}
}
Here is my take: The smallest palindrome follows two conditions either a[i] == a[i-1](AA scenario) or a[i] == a[i-2](ABA scenario).
First using the above conditions we can find a minimal size palindrome. expand it on both sides till it follows palindrome property. Compare this expanded palindrome with the global largest palindrome variable, and update the largest palindrome.
Now we can optimise it further by taking analogy from pattern matching. We can calculate the next jump (from where we will start the next find minimal palindrome) while expanding the minimal palindrome itself.
Time-o(nlogn)
It is DP. And it is O(n^2). There are two variables in the recursion which go from 0-n/2 and n/2 to end.. Worst case is n/2 X n/2 which makes it O(n^2)
One simplest solution I can think of find longest common substring between S and Reverse (S) and this can be find by using suffix tree in O(n) and O(n^2) from dynamic programming
- fat0ss August 29, 2010