## Amazon Interview Question for Member Technical Staffs

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 5 vote

The logic is:
Since the palindrome can appear in any place in the long string, start with the complete string and check if it is a palindrome.
If found, we are done,
If palindrome not found, reduce string length by 1 and perform a sliding window on the input to check if it is a palindrome.
Example:

String Length: 7
Longest String: "eabcbad". Result: not a palindrome.

String Length: 6
Longest String: "eabcba". Result: not a palindrome.
Longest String: "abcbad". Result: not a palindrome. (Slide the window to get next 6 character length string in the input string)

String Length: 5
Longest String: "eabcb". Result: not a palindrome.
Longest String: "abcba". Result: FOUND PALINDROME. This is the longest length palindrome.

Here is the recursive code for finding:

``````public class LongestPalindromeInString {

public static void main (String[] args) {

findSubString(input, input.length(), "");
}

private static String findSubString(String str, int len, String longestPalindrome) {

if(len == 1) {
//If we reach here, that means, no palindrome found. We wont consider single characters as palindrome themselves.
System.out.println("Palindrome longer than 1 character is not found in the input = " + str);
return "";
}

//Since we are going from longer length to smaller length, this if is to ignore all the other recursive calls once the palindrome is found with length greater than 0
if(len < longestPalindrome.length()) return "";

boolean isPalindrome = false;

for(int i=0; i<str.length()-len+1; i++) {
isPalindrome = isPalindrome(str.substring(i, i+len));

if(isPalindrome) {
System.out.println("Longest Palindrome found in " + str + " is " + str.substring(i, i+len));
longestPalindrome = str.substring(i, i+len);
}
}

//recursive call to get the next set of strings by reducing length by 1
findSubString(str, --len, longestPalindrome);

return str;
}

/*This method finds if the given string is a palindrome */
private static boolean isPalindrome (String str) {
if(str == null || str.length() == 0) return false;

int i=0;
int j = str.length()-1;
while(i<j) {
if(str.charAt(i) != str.charAt(j)) {
return false;
} else {
i++;
j--;
}
}
return true;
}
}``````

Here is the output of the program:

O/P: Longest Palindrome found in eabcbadd is = abcba

For String: "abcdef"
O/P: Palindrome longer than 1 character is not found in the input = abcdef

Comment hidden because of low score. Click to expand.
0

I don't think this will work when the longest palindrome is obtained by ignoring characters from the end. To handle these cases, you need to have a sliding window moving from right to left as well.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int lps(char *str, int n)
{
if (*str==*(str+n))
return 1;
if (*str == *(str+n) && strlen(str)==2)
return 2;
if (*str == *(str+n))
return lps (*(str+1), n-1) + 2;
return max( lps(*str, n-1), lps(*(str+1), n) );
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

int lps(char *str, int n)
{
if (*str==*(str+n))
return 1;
if (*str == *(str+n) && strlen(str)==2)
return 2;
if (*str == *(str+n))
return lps ((str+1), n-1) + 2;
return max( lps(str, n-1), lps((str+1), n) );
}

Comment hidden because of low score. Click to expand.
0

HardCode plz check your code on some samples i am sure u will understand your problem what mistake u doing....this question asked to that mistake bcoz many people do it.....

abcdefba for this sample i think your code will return 4 but here only 1 len palindrome strings......check your code against some samples

Comment hidden because of low score. Click to expand.
0

The code you have written is for the longest palindrome subsequence i guess...not the longest palindrome substring.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I came up with a solution without recursion. It takes O(n^2) time.

``````#include<stdio.h>
int LPS(char *s,int n);
int main()
{
char array[100];
char c;
int i = 0;
c = getchar();
while(c!='\n')
{
array[i++]=c;
c = getchar();
}
array[i] ='\0';
int n = i;
int l = LPS(array,n);
printf("%d\n",l);
return 0;
}
int LPS(char *s,int n)
{
int x = 0;
int i ,k = 2;
int count = 1;
int max = -500;
int j = 0;
for(i=1;i<n-1;i++)
{
if(s[j]==s[k] && j>=0 && k<=n-1)
{
count += 2;
j--;
k++;
i--;
if(count > max)
{
max = count;
}
if(j<0)
{
count = 1;
i = k-2;
j = i;
}
}
else if(s[k]==s[i])
{
count += 1;
k++;
i--;
if(count > max)
{
max = count;
}
}
else
{
k++;
i = k-2;
j = i;
count = 1;
}
}
if(count>max)
{
max = count;
}
return max;
}``````

Comment hidden because of low score. Click to expand.
0

This is not recursion and my question is specific to recursion.......

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def longestPalindromeRecursive(s):
if isPalindrome(s):
return s
return max([longestPalindromeRecursive(s[1:])] + [longestPalindromeRecursive(s[:-1])], key=len)

def isPalindrome(s):
for i in range(len(s) / 2):
if s[i] != s[-i-1]:
return False
return True

print longestPalindromeRecursive("aabazzzz")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

With better formatting (python):

``````def LPS(s):
if isPalindrome(s):
return s
return max([LPS(s[1:])] + [LPS(s[:-1])], key=len)

def isPalindrome(s):
for i in range(len(s) / 2):
if s[i] != s[-i-1]:
return False
return True

print LPS("aabazzzzazzz")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think my code will works and I use Manacher's algorithm. For more information, search this algorithm and you will know how it works.

``````#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;

class LGSTPalinddromeFinder
{
public:
string longestPalindrome(string s)
{
size_t n = s.length();
if(n<=1)
{
return s;
}

string ms = "\$#";
for(int i=0; i<n; i++)
{
ms.append(1, s[i]);
ms.append(1, '#');
}

int m = (int)n*2+2;
vector<int> pa(m, 0);

int maxi=0, id=0, mi = id+pa[id];

for(int i=1; i<m-1; i++)
{
if(i >= mi)
{
pa[i] = 0;
}
else
{
if(pa[2*id-i] < pa[id]+id-i)
{
pa[i] = pa[2*id-i];
continue;
}
else
{
pa[i] = pa[id]+id-i;
}
}

while(ms[i-pa[i]-1] == ms[i+pa[i]+1])
{
pa[i]++;
if((i+pa[i]+1) >= ms.size())
{
break;
}
}

if(i+pa[i]>mi)
{
id = i;
mi = id + pa[id];
}

if(pa[i]>pa[maxi])
{
maxi = i;
}
}

string r;
int left = maxi - pa[maxi], right = maxi + pa[maxi];

for(int i = left; i<=right; i++)
{
if(ms[i] != '\$' && ms[i] != '#')
r.append(1, ms[i]);
}

return r;

}
};

int main(int argc, const char * argv[])
{

// insert code here...
string s;
cin >> s;
LGSTPalinddromeFinder so;
string r = so.longestPalindrome(s);
cout<<r<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

I don't remember to do that by recursion! Sorry about that!!!!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we reverse the string and find LCS of reverse string and original string ??

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes, this logic will work but there is a common mistake that people make in this logic.
If the original string has a non palindrome substring and a reverse copy of the non palindrome substring than the logic fails.

example: consider string abacxycaba. The reverse of the string is "abacyxcaba" So the LCS would be abac. But thats not a palindrome.

We can quickly fix this issue though. Each time we find a LCS candidate, we check if the substringâ€™s indices are the same as the reversed substringâ€™s original indices. If yes then its not a palindrome else we found one.

Time complexity of LCS solution is O(N^2) though.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>

int LPS(char *str, int N)
{
int i;
int l=0;
int l1=0;
int l2=0;

if (N<=1)
return 1;
if(str[0] == str[N-1])
{
l=1;
while(i < (N-1-i))
{

if(str[i] != str[N-1-i])
{
l=0;
break;
}
i++;
}

}
if (l>0)
return N-1;
l1=LPS(str+1,N-1);
l2=LPS(str,N-1);

return (l1>l2?l1:l2);
}

int main()
{
printf("length %d\n",LPS(str,14));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>

int LPS(char *str, int N)
{
int i=0;
int l=0;
int l1=0;
int l2=0;

if (N<=1)
return 1;
if(str[0] == str[N-1])
{
l=1;
while(i < (N-1-i))
{

if(str[i] != str[N-1-i])
{
l=0;
break;
}
i++;
}

}
if (l!=0)
return (N%2 == 0)? 2*i : 2*i+1;
l1=LPS(str+1,N-1);
l2=LPS(str,N-1);

return (l1>l2?l1:l2);
}

int main()
{
char str[]="xabccbav";
printf("length %d\n",LPS(str,8));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>

bool
isPalindrome(const std::string& input) {
for( int i=0, j=input.length()-1; i<j; i++,j--) {
if(input[i] != input[j]) {
return false;
}
}
return true;
}

std::string
LPS(const std::string& input) {
if(input.length() < 2 ) {
return "";
}

if(isPalindrome(input)) {
return input;
}

std::string leftLps = LPS(input.substr(1,input.length()-1));
std::string rightLps = LPS(input.substr(0,input.length()-1));

if(leftLps.length() > rightLps.length()) {
return leftLps;
}
else {
return rightLps;
}

}

/* Driver Program */

int
main(int argc, char **argv) {
std::string input;
std::cin >> input;
std::cout << LPS(input);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int max(int a, int b){
if (a>b) return a;
else return b;
}

//39eabajdk3kabbbajdhjcjcjcj
int LPS(char *str1, int n){
if (n == 0) return 0;
int i = 0;
int j = n - 1;
int p_len = 0;
int max_len = 0;
while (j > 0){
if (str1[i] == str1[j]){
if (i == j || j == i+1) {
p_len++;
if (p_len > max_len){
max_len = p_len;
break;
}
}
else {
p_len += 2;
}
i++;
j--;
}
else{
i = 0;
p_len = 0;
j--;
}

}
//printf("str1 is %s, max_len is %d\n", str1, max_len);
return max(max_len, LPS(str1+1, n-1));

}

int main() {
char *str1 = "39eabajdk3kabbbajdhjcjcjcj";
printf("max LPS is %d\n", LPS(str1, strlen(str1)));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

str="abcdefghgfedcba"
l=len(str)-1
i=0
def getcn(str,i,j):
while i<j:
if str[i]!=str[j]:
return 'n'
i+=1
j-=1
return 'y'
def checkP(str,i,l):
if i>=l:
list1=[0,0]
return list1
else:
list1=checkP(str,i+1,l)
if (l-i)>(list1[1]-list1[0]):
for m in range(l,i,-1):
if str[i]==str[m]:
y=getcn(str,i,m)
if y=='y':
if (m-i)>(list1[1]-list1[0]):
list1=[i,m]
return list1
list1=checkP(str,i,l)
if list1[0]==list1[1]:
print "No pallindrome"
else:
for i in range(list1[0],list1[1]+1):
print str[i],

Comment hidden because of low score. Click to expand.
0
of 0 vote

Best case: O(1)
otherwise: O(n*n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string ss;
void LSP(string s, int i, int length, int n){

ss = "";
if((i+length)>n){
return;
}
string r;
ss.assign(s, i, length);
r=ss;
reverse(r.begin(), r.end());
if(r==ss)
return;

LSP(s, i+1, length, n);
}
int main(){

int n = s.length();
int len=n;
while(len){
LSP(s, 0, len, n);
//cout<<len<<" "<<lsp<<endl;
if(ss!=""){
cout<<ss<<endl;
break;
}
len--;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Int getLongestPalindromeLength(char inputString[], int start, int end)
{
If(start == stop) return 1;
Int i = start, j = stop;
for(; i< j; i++ ){
If(inputString[i] != inputString[j])
Break;
i++; j--;
}
If(i == j) return (Start - stop + 1);
getLongestPalindromeLength(inputString[], start-1, stop);
getLongestPalindromeLength(inputString[], start, stop -1);
getLongestPalindromeLength(inputString[], start-1, stop -1);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Int getLongestPalindromeLength(char inputString[], int start, int end)
{
If(start == stop) return 1;
Int i = start, j = stop;
for(; i< j; i++ ){
If(inputString[i] != inputString[j])
Break;
i++; j--;
}
If(i == j) return (Start - stop + 1);
getLongestPalindromeLength(inputString[], start-1, stop);
getLongestPalindromeLength(inputString[], start, stop -1);
getLongestPalindromeLength(inputString[], start-1, stop -1);
}

Comment hidden because of low score. Click to expand.
0

@nav i dont think getLongestPalindromeLength(inputString[], start-1, stop -1); is necessary since the recursive call of start -1's stop-1 will cover that

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a working code in C++

``````#include <stdio.h>

int max_ps(char* str, int n, int max);
bool is_palindrome(char *str, int n);

int LPS(char *str, int n)
{
return max_ps(str, n, 0);
}

int max_ps(char* str, int n, int max)
{
int lmax = 0;
int rmax = 0;

if (n == 0)
{
return max;
}

if (is_palindrome(str, n) && n > max)
{
max = n;
}

lmax = max_ps( str+1, n-1, max);
rmax = max_ps(str, n-1, max);

if (lmax > max)
max = lmax;

if (rmax > max)
max = rmax;

return max;
}

bool is_palindrome(char *str, int n)
{
int s = 0;
int e = n-1;

while(s < e)
{
if (*(str+ s++) != *(str + e--))
{
return false;
}
}
return true;
}

int main()
{
char * a = "aaacyoomimooyiabb";
int max = 0;
max = LPS(a, 17);

printf ("max lps = %d\n", max);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findLongestPalindromicSub(String str,int i, int j)
{
if(i>=j) return 0;

if(str.charAt(i)==str.charAt(j))
return 2 + findLongestPalindromicSub(str,i+1,j-1);

return Math.max(findLongestPalindromicSub(str,i+1,j),
findLongestPalindromicSub(str,i,j-1));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

a

Comment hidden because of low score. Click to expand.
0
of 0 vote

non-recursive solution if that matters..

``````public static string LongestPalindromeSubstring(string s)
{
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
string s_r = new string(charArray);
string palindrome = "";
for (int i = 0; i < s.Length; i++)
{
string prevSubPalin = "";
string currSubPalin = "";
for (int j = i; j < s.Length; j++)
{
if (s[j] == s_r[j - i])
{
currSubPalin = string.Concat(currSubPalin, s[j].ToString());
}
else
{
if (prevSubPalin.Length < currSubPalin.Length)
prevSubPalin = currSubPalin;
currSubPalin = "";
}
}

if (prevSubPalin.Length < currSubPalin.Length)
prevSubPalin = currSubPalin;

if (palindrome.Length < prevSubPalin.Length)
palindrome = prevSubPalin;
}

return palindrome;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

aaasubusa> Lot of the algos above fail, as the assume the middle element is at the center of the array. For the problem it can be anywhere, for this eg, it is at Index 5.

Iterative is simple, for each Array Element, you start with it as the middle or if it +1 is the same, it and it+1 as the middle, iteratively stetch out either sides and end when you dont. Calculate the palindrome length for all elements as mid, max it.

Recurisve I probably dont see the point
For each Index as the middle
int length = Call isPalindromeWithMid with Increased Lengths starting from Index to left and right.
if Length > max update variables.

int IsPalindromeWithMid(mid, left, right)
If Left and right match
return 1 + IsPalindromeWithMod(mid, left-1, right+1)
else retunr 0;

Recursive IsPalindrome seems like a total waste of memory in terms of replacement for the iterative approach. But the question does says recursive,. I would definitely point this over to the interviewer.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.