Amazon Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
Algorithm:
Use Dynamic programming
LP(i,j) = 1 if i = j e.g A
= 1 if i = j-1 AND a[i] != a[j] e.g AB
= 2 if i = j-1 AND a[i] == a[j] e.g AA
= LP(i+1 , j-1) + 2 if i != j-1 AND a[i] == a[j] e.g: ABCBA i =0 and j=4
= max{ LP[i+1,j], LP[i,j-1]} if i != j-1 AND a[i] != a[j] e.g MNOPQ i=0 and j=4
Note: copied from the wiki
Nice solution. The DP solution can provide you the longest palindrome present in the given string. However, I wonder, how you would trace the DP table to print ALL the palindromes available.
There are 2 cool solutions available for this problem at:
stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree
The solution using suffix arrays is complete and is very well explained.
For any palindrome you can consider the cases:
a. If start and end index are same in a string that is i==j then return 1.
b. if at any position i and j string[i]==string[j] and i+1==j then return 2.
c. if at any position i and j string[i]==string[j] then
return longestPalindrome(string,i+1,j-1)+2 //this is the case for 2 length palindromes.
return max(longestPalindrome(string,i,j-1),longestPalindrome(string,i+1,j))
Using DP, my code is based on Java. The time complexity is O(n^2)
public static int[] getLongest(String str){
char[] data = str.toCharArray();
int[] index = new int[data.length];
int[] buffer = new int[256]; //store pre index
int max = 0;
int[] span = new int[2];
for(int i = data.length - 1; i >= 0; i--){
index[i] = buffer[data[i]] == 0 ? -1 : buffer[data[i]];
buffer[data[i]] = i;
}
for(int i = 0; i < index.length && index[i] != -1 ; i++){
int cur = i;
int j = index[i];
while(j != -1){
for(; j != -1; j = index[j]){
if(isPaloindromes(data,cur,j) == true){
if(max < j - cur + 1){
max = j - cur + 1;
span[0] = cur;
span[1] = j;
}
}
}
int tmp = cur;
index[tmp] = -1;
cur = index[cur];
j = cur == -1 ? -1 : index[cur];
}
}
return span;
}
public static boolean isPaloindromes(char[] data, int i, int j){
int mid = (i + j) / 2;
for(int k = 0; k < mid; k++){
if(data[i + k] != data[j - k])
return false;
}
return true;
}
Another solution with O(n^2) worst case.
static void MaxPalindrome(string str)
{
int n = str.Length;
int max = 1;
for (int i = 0; i < n-1; i++)
{
int s = 0;
int e = 0;
int cnt = 0;
if (i>0 && str[i - 1] == str[i + 1]) // odd palindrome
{
s = i - 2;
e = i + 2;
cnt = 3;
}
else if (str[i] == str[i + 1]) //even palindrome
{
s = i - 1;
e = i + 2;
cnt = 2;
}
else
{
continue;
}
while (s >= 0 && e < n)
{
if (str[s] != str[e])
break;
s--;
e++;
cnt = cnt + 2;
}
Console.WriteLine("\n Palindrome:");
for (int k = s + 1; k <= e - 1; k++)
Console.Write(str[k] + "\t");
if (cnt > max)
max = cnt;
}
Console.WriteLine("\n Max Palindrome Length:" + max);
}
#find a way to separate this into chunks
def palindromes(string):
#smallest palindrome, 2 letters spelled the same when interchanged, e.g aa bb etc,
#so compare chars one by one till you get a palindrome or till you get to the end
# of list
string = string.lower()
word =''
longest=''
for i in range(len(string)-1):
word+=string[i]
j=i+1
while not palindrome(word) and j<len(string)-1:
word+=string[j]
j+=1
if palindrome(word) and (len(longest) < len(word)):
longest = word
word=''
return longest
#function to determine palindrome
def palindrome(word):
if len(word) <= 1 :
return False
for i in range(len(word)):
if word[i] == word[(len(word)-1) - i]:
flag = True
else:
return False
return flag
if __name__=='__main__':
print (palindromes('abfdRacecaRAbAorTITabcdef'))
1]Take the string as an input
2] split it into odd and even numbered characters
3] create a even char string half of count of even characters(this would help in generating a smaller permutation subset)
4] Generate all possible permutations of an even number subset(using dynamic programming)
5] use this list to generate the pallindrome by reversing each string and appending at the end(use odd number characters in the middle of the string).
Below is the implemented code for the same.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
void FindEvenAndOddNumberedCharacters(const string &strInput,string& strEvenCharString,string& strOddCharString);
typedef vector<string> stringVect;
stringVect GenerateSubSets(string setVals,int nIdx);
void GeneratePallindromes(string strEvenCharString,string strOddCharString);
int _tmain(int argc, _TCHAR* argv[])
{
string strInput = "abfdRacecaRAbAorTITabcdef";
string strEvenCharString, strOddCharString;
FindEvenAndOddNumberedCharacters(strInput,strEvenCharString,strOddCharString);
cout << "Odd Characters: " <<strOddCharString <<endl <<"Even Characters : "<<strEvenCharString << endl;
cout << "Max Len Pallindrome : "<< strEvenCharString.length()*2 +1 << endl;
GeneratePallindromes(strEvenCharString,strOddCharString);
std::getchar();
return 0;
}
/*
spit out the pallindromes
*/
void GeneratePallindromes(string strEvenCharString,string strOddCharString)
{
int nTotPallinCount=0;
stringVect vOnesidePallindromes = GenerateSubSets(strEvenCharString,0);
for(auto strOneSidePallin:vOnesidePallindromes)
{
string strReversePallin(strOneSidePallin);
std::reverse(strReversePallin.begin(), strReversePallin.end());
cout << strOneSidePallin<<strReversePallin<<endl;
nTotPallinCount++;
// take into condsideration the odd characaters use them at the center of the string to pivot around the same.
for(auto iter= strOddCharString.begin();iter != strOddCharString.end();iter++)
{
cout << strOneSidePallin<<*iter<<strReversePallin<<endl;
nTotPallinCount++;
}
}
cout << "Total Pallin Drome Count : " <<nTotPallinCount<< endl;
}
/*
Find out all the odd and even characaters so that they can be used to generate a pallin drome
*/
void FindEvenAndOddNumberedCharacters(const string &strInput,string& strEvenCharString,string& strOddCharString){
map<char,int> charNoMap;
// get to each character and get a count of each of the characters
for(auto iter= strInput.begin();iter != strInput.end();iter++)
{
charNoMap[*iter]++;
}
// count the characters if they are odd or even if even pick the even stream and push to pallindrome list
// if odd then just pick 1 character in odd list and push the rest into the even list.
for (auto iter : charNoMap)
{
int nCount = iter.second ;
if(nCount % 2 != 0) // if odd count
{
strOddCharString+=iter.first;
nCount--;
}
if(nCount>0)
{
// just spit out half of the even characters to help create pallindromes
for(auto i=0 ;i<nCount/2;i++) strEvenCharString+=iter.first;
}
}
}
/*
Use dynamic programming to generate the string subsets which can then be used to generate pallindromes
*/
stringVect GenerateSubSets(string setVals,int nIdx){
stringVect retStringVect;
if(setVals.length() == nIdx){
retStringVect.push_back(string()); // pushing empty vector
}
else{
retStringVect = GenerateSubSets(setVals,nIdx+1);
auto nItem = setVals[nIdx];
stringVect tempvect;
for(auto vect:retStringVect)
tempvect.push_back(vect);
for(auto iter = tempvect.begin();iter != tempvect.end();iter++){
iter->push_back(nItem);
}
for(auto vect:tempvect)
retStringVect.push_back(std::move(vect));
}
return retStringVect;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace StringExamples
{
class Program
{
public static void Main(string[] args)
{
FindLongestPalindrome();
}
public static void FindLongestPalindrome()
{
string couldbePalindromes = "abdfRacecaRAbAorTITabcdef";
int palinLength = 2;
int longestPalin = 2;
string longestPalindrome = null;
bool isPalin = false;
while (palinLength < couldbePalindromes.Length / 2)
{
for (int j = 0; j < couldbePalindromes.Length - palinLength; j++)
{
char[] arrayforPalin = new char[palinLength + 1];
for (int i = j, k = 0; i <= palinLength + j; i++, k++)
{
arrayforPalin[k] = couldbePalindromes[i];
}
string couldbePalin = new string(arrayforPalin);
isPalin = CheckForPalindrome(couldbePalin);
if (isPalin == true)
{
Console.WriteLine("We found one palindrome {0} with length {1}", couldbePalin, couldbePalin.Length);
if (couldbePalin.Length > longestPalin)
{
longestPalin = couldbePalin.Length;
longestPalindrome = couldbePalin;
}
}
}
palinLength = palinLength + 1;
}
Console.WriteLine("Longest Palin was of length {0}, {1}", longestPalin, longestPalindrome);
Console.ReadLine();
}
public static bool CheckForPalindrome(string checkforPalin)
{
Stack<char> testPalin = new Stack<char>();
bool isPalin = false;
int i = 0;
if (checkforPalin.Length % 2 == 1)
{
while (i < checkforPalin.Length / 2)
{
testPalin.Push(checkforPalin[i]);
i++;
}
i = (checkforPalin.Length / 2) + 1;
while (i < checkforPalin.Length)
{
char charCompare = testPalin.Pop();
if (charCompare == checkforPalin[i])
{
i++;
isPalin = true;
}
else
{
isPalin = false;
break;
}
}
}
if (checkforPalin.Length % 2 == 0)
{
while (i < checkforPalin.Length / 2)
{
testPalin.Push(checkforPalin[i]);
i++;
}
while (i < checkforPalin.Length)
{
char charCompare = testPalin.Pop();
if (charCompare == checkforPalin[i])
{
i++;
isPalin = true;
}
else
{
isPalin = false;
break;
}
}
}
return isPalin;
}
}
}
I don't have the time to code this now, but I think this can be done in O(N) time by using a stack. Scan each character from the string and push it on to the stack. When you push, just compare the newly scanned char to the top and the second char on the stack. If the new char matches any of the two, it might be the beginning of a palindrome. In which case, pop the top two chars and arrange the newly scanned char and the top two popped chars into a String. Now keep scanning new chars and compare them with the top of the stack. As the palindrome continues, the algo will keep finding matching chars on the top of the stack. Keep popping them and adding them to the beginning and end of the String you have started. The palindrome run ends when a newly scanned char doesn't match the top of the stack, or if the stack is empty. You have just found a palindrome. Put it into a priority queue sorted by string length. Set some flags in your algorithm to indicate that the palindrome run has ended, and empty your stack completely and continue to scan the rest of the chars in the String. Repeat the above process to find more Palindromes. Watch out for even versus odd length palindromes. Once the input string has been scanned, you have found all the palindromes and the priority queue should bring the longest one to the top.
Known best solution for longest palindrom 0(n) "akalin.cx/longest-palindrome-linear-time", I found the idea is quite similar to string matching in that we need to restart the search where it is most make sense (to give a potential better result). While DP solution is generally used, the solution is not any better than a simple solution that consider all position a potential center of the palindrome and then extend its two-ends to the maximal length.
- LinhHA05 July 24, 2013