Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Is aaabbb considered a palindrome? I thought it was restricted to things in the form of aabbbaa
Can you elaborate on the O(N) solution?
1. loop through 1 to 2n-1 ? 2n-1? it will be out of range
2. check on each location possible palindromes. what do you mean?
1 to 2n-1 is just imaginary (2n-3 is better). Take "AABB" for example, imagine "A1A3B5B" looping from 1 to 5. at loop counter 1, get palindrome "AA"; at 2, get nothing as AAB is not palindrome; at 3, get "AABB"; at 4, get nothing due to ABB; at 5, get palindrome "BB".
Here's working C# code:
public static int FindLongestPalindromeSubsequence_X(string s)
{
int maxLen = 0;
for (int i = 1; i < 2 * s.Length - 2; i++)
{
int low;
int high;
if (i % 2 != 0)
{
low = i / 2;
high = low + 1;
}
else
{
low = i / 2 - 1;
high = low + 2;
}
int curLen = 0;
while (low >= 0 && high < s.Length)
{
if (s[low] == s[high])
{
string currentPalindrome = s.Substring(low, high - low + 1);
Console.WriteLine("FindLongestPalindromeSubsequence_X: " + currentPalindrome);
curLen = high - low + 1;
if (curLen > maxLen)
{
maxLen = curLen;
}
low--;
high++;
continue; // Not really necessary;
}
else
{
break;
}
}
}
return maxLen;
}
Xiang,
How could AAABBB be a palindrome? Only AABBAA is a palindrome. Please correct me if I'm wrong.
@Xiang,
Can you please tell me the output of your program. I am not getting correct output.
if the question is related to max subSequence palindrome then output would be
12345gfg/gfg54321 of length 16
Well my code just prints maxlength
private static int FindLongestPalindrom(String string) {
return FindLongestPalindrom(string.toCharArray(),0,string.length()-1);
}
private static int FindLongestPalindrom(char[] s, int i, int j) {
if(i==j)
return 1;
else if(i==j+1){
if(s[i] == s[j]){
return 2;
}else{
return 1;
}
}else if(s[j] == s[i+1])
return FindLongestPalindrom(s, i+1, j-1)+2;
else
return Math.max(FindLongestPalindrom(s, i+1, j), FindLongestPalindrom(s, i, j-1));
}
We might still improve by using memoization.
There is an O(n) algorithm to find the longest palindrome
Named Manacher Algorithm.
Reference:( you should add "." in the address)
zhuhongcheng wordpress com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
If you can read chinese then you can go to:
www cnblogs com/a180285/archive/2012/03/03/Manacher_Algorithm.html
The array is unsorted therefore it will take O(n) to search for duplicated elements, once you find one call a function to check if the elements next to them form a palindrome, if so save it. The biggest palindrome possible should be n/2 so the worst case is quadratic, but not likely in practice.
After save it just check which one of your saved palindromes is the biggest and return it.
dynamic programming
dp[start][end] -> number of letters
dp[start][end] =
case start>end -> 0
case start =end -> 1
case ch[start]==ch[end] -> 1+dp[start+1][end-1]
case ch[start]!=ch[end] -> max(dp[start+1][end],dp[start][end-1])
Based on your algorithm, the longest sequence in the above example has length 16, which gives "12345gfg/gfg54321".
Revise: the last sentence change to
case ch[start]!=char[end] -> 0
Please comment.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{ int n,max=0;
char s[30];
cout<<"enter the string\n";
for(int i=0;i<20;i++)
cin>>s[i];
for(int i=0;i<20;i++)
{ int count=0,max1=0;
for( int j=i,m=19;j<=m;)
{ if(s[j]==s[m])
{count++;j++;m--;
if(max1<count)
max1=count;
}
else
{ break;}
}
if(max<max1)
max=max1;
}
cout<<"max of palindrome length is"<<max<<"\n";
system("pause");
return 0;
}
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define bool int
#define true 1
#define false 0
typedef struct maxSegment{
int a;
int b;
}MAXSEGMENT;
int findReverseStr(char a[], int s1, int s2, int d1, int d2)
{
if(s2<s1 || d2<d1 || a==NULL)
return false;
if((s2-s1) > (d2-d1))
return false;
int n = s2-s1+1;
int i,j=0;
for(i=d2; i>=d1; i--)
{
if(j>=n)
return 1;
if(a[i] == a[j])
{
j++;
}else
{
j=0;
}
}
return 0;
}
main()
{
char a[]="12345gsfggd541fhgs54321fgsdh";
int n = strlen(a);
int i, j, k;
MAXSEGMENT maxseg;
maxseg.a=0;
maxseg.b=0;
for(k=0; k<n; k++)
{
for(i=k; i<n/2+1; i++)
{
//find reverse string of a[k..i] from a[i+1..n]
if(findReverseStr(a, k, i, i+1,n-1))
{
if((i-k)>(maxseg.b-maxseg.a))
{
maxseg.a=k;
maxseg.b=i;
}
}
}
}
for(i=maxseg.a; i<=maxseg.b; i++)
printf("a[%d]=%d ", i, a[i]);
printf("\n\r maxseg.a=%d, maxseg.b=%d", maxseg.a, maxseg.b);
/*
if(findReverseStr(a, 0, 4, 5,27))
printf("yeah");*/
}
How about using two pointers ??
Algo :
1. Keep one pointer at start and other at the end.
2. Move first pointer and move second pointer until it finds element pointer by first.
3. If first and second points to same element then exit
4. If it does find a hit then keep track of indexes which are matched.
This is similar to reversing a string, but with out using extra string object.
One of my friends was asked this question;
The interviewer wanted a O(n2) solution with no extra space.
Algorithm that he told me that I think works goes something like this:
for each character in the array
{
start checking from the end of the array towards the start to see if there is a substring present while keepinf track of the largest substring found so far.
}
Reverse the string, and then find the longest common subsequence using a suffix tree. That's N^2 but looks very straightforward.
- Xiang October 10, 2012The most efficient way I think is to loop through 1 to 2n-1 (n being string len), and check on each location possible palindromes. 1 to n is not right as it will miss mirrored palins like AAABBB. This is essentially O(N) with worst case having all same chars.