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:
in input string "eabcbad"

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) {
		String input = "eabcbadd";
		
		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:

For String: "eabcbadd"
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

- Saurabh July 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

For example: abcbad

- sks August 17, 2014 | Flag
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) );
}

- HardCode July 04, 2014 | Flag Reply
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) );
}

- HardCode July 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kavita July 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sai July 07, 2014 | Flag
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;
}

- Ajay July 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kavita July 04, 2014 | Flag
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")

- Brandy July 04, 2014 | Flag Reply
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")

- Brandy July 04, 2014 | Flag Reply
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;
}

- gzyeli123 July 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gzyeli123 July 05, 2014 | Flag
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 ??

- Rakesh July 05, 2014 | Flag Reply
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.

- Saurabh July 05, 2014 | Flag
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()
{
    char str[]="aasaaddsdsddsg";
    printf("length %d\n",LPS(str,14));
return 0;
}

- Anonymous July 05, 2014 | Flag Reply
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;
}

- Anonymous July 05, 2014 | Flag Reply
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;
}

- A K M Mahmudul Hoque July 06, 2014 | Flag Reply
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)));
}

- dato123 July 06, 2014 | Flag Reply
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],

- Aalekh Neema July 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Aalekh Neema July 10, 2014 | Flag Reply
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(){


string s="eabcbad";
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--;
}
}

- Anonymous July 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recurssion can be used,

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);
}

- nav July 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recurssion can be used,

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);
}

- nav July 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Phoenix July 14, 2014 | Flag
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;
}

- hankm2004 July 16, 2014 | Flag Reply
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));
}

- Dhawal July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a

- Anonymous July 24, 2014 | Flag Reply
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;
}

- ShaRai August 16, 2014 | Flag Reply
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.

- ssubbu August 16, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More