Amazon Interview Question Java Developers
Country: United States
Interview Type: In-Person
Dynamic programming , runs in O(n^2) though.
public static String longestPal(String a) {
// create new array to hold results
int[][] arr = new int[a.length() + 1][a.length() + 1];
// reverse string a
String b = new StringBuffer(a).reverse().toString();
// complete the Longest common subsequence array
for (int i = 0; i < a.length(); i++) {
for (int j = 0; j < b.length(); j++) {
if (a.charAt(i) == b.charAt(j)) {
arr[i + 1][j + 1] = arr[i][j] + 1;
} else {
arr[i + 1][j + 1] = Math.max(arr[i + 1][j], arr[i][j + 1]);
}
}
}
String str = "";
int x = a.length();
int y = b.length();
//trace back form bottom of LCS array
while (x > 0 && y > 0) {
if (arr[x][y] == arr[x - 1][y]) {
x--;
} else if (arr[x][y] == arr[x][y - 1]) {
y--;
} else {
if (a.charAt(x - 1) == b.charAt(y - 1)) {
str += a.charAt(x - 1);
x--;
y--;
}
}
}
// return the largest palindrome
return str;
}
do not work with:
String = "abbabbaxabbabba toppottoppottoppot abbabbayabbabba";
expected = "abbabba toppottoppottoppot abbabba";
import org.junit.Before;
import org.junit.Test;
public class palindromeClass{
@Test
public static String longestPalindromeString(String in) {
char[] input = in.toCharArray();
int longestPalindromeStart = 0;
int longestPalindromeEnd = 0;
for (int mid = 0; mid < input.length; mid++) {
// for odd palindrome case like 14341, 3 will be the mid
int left = mid-1;
int right = mid+1;
// we need to move in the left and right side by 1 place till they reach the end
while (left >= 0 && right < input.length) {
// below check to find out if its a palindrome
if (input[left] == input[right]) {
// update global indexes only if this is the longest one till now
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
// for even palindrome, we need to have similar logic with mid size 2
// for that we will start right from one extra place
left = mid;
right = mid + 1;// for example 12333321 when we choose 33 as mid
while (left >= 0 && right < input.length)
{
if (input[left] == input[right]) {
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
}
// we have the start and end indexes for longest palindrome now
return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
}
public static void main(String args[]){
System.out.println(longestPalindromeString("abbabbaxabbabba toppottoppottoppot abbabbayabbabba"));
}
}
At every step we find the possible string combinations by removing a character from the string.
Check each combination for palindrome.
For Example:
Input: 'cabad'
Output: 'aba'
1. check 'cabad' for palindrome
2. check 'caba', 'abad' for palindrome (combinations of reducing one character from the given string)
3. check 'cab','aba','bad' for palindrome (continuous sequences after reducing two character from the given string)
We return 'aba'
def isPalindrome(word):
i = 0
j = len(word) - 1
while i < j:
if word[i] != word[j]:
return False
i+=1
j-=1
return True
def longestPalindrome(string):
length = len(string)
maxLength = len(string)
while maxLength > 1:
start = 0
while start <= length - maxLength:
end = start + maxLength
if isPalindrome(string[start:end]):
return string[start:end]
start += 1
maxLength -= 1
return False
dynamic programming should work...Run time is O(n2)
Define Matrix m[1....n,1...n] where m[i,j] is length of longest palindrome in string x[i,j] (The given String).
m[i,j]=0 if i>j
1 if i=j
m[i+1,j-1]+2 if (i<j and x[i]=x[j] and x[i+1]=x[j-1])
else
max(m[i+1,j],m[i,j-1])...
fill all entries below main diagonal by 0 first then fill the main diagonal elements of the matrix with 1 and then start filling the upper triangle...
After That m[1,n] will be length of longest palindrome....
I think the algorithm is correct but not sure....
Dynamic Programming:
m[i,j]="" where i>j
m[i,j]=str(i) where i=j
m[i,j]="" where j-i+1=2 and str(i) != str(j)
m[i,j]=m[i+1,j-1] where j-i+1=3 and str(i) != str(j)
m[i,j]=string[i,j] where j-i+1=2 and str(i) = str(j)
m[i,j]=string[i,j] where j-i+1=3 and str(i)=str(j) and str(i+1)=str(j-1)
m[i,j]=string[i,j] where m[i,(j-i)/2-1] = m[(j-1)/2,j] and j-i+1>=4
m[i,j]=max_palindrome( m[i, i+k], m[i+k+1, j] ) where j-i+1>=4 and 1<=k<=j-i-1 and m[i,(j-i)/2-1] != m[(j-1)/2,j]
Longest palindrome is then in m[0,string.length()-1];
package com.bala.logical;
public class Polindrome {
public static void main(String[] args) {
String bigString = "aaabbaaaccdeqjncsdddmmmkkkmmmddd";
String bigPoli = "";
for (int i = 0; i < bigString.length(); i++) {
for (int j = i + 1; j < bigString.length() ; j++) {
String s = bigString.substring(i, j);
if (isPolindrome(s)) {
if (s.length() > bigPoli.length()) {
bigPoli = s;
}
}
}
}
System.out.println(bigPoli);
}
public static boolean isPolindrome(String s) {
boolean poli = false;
String a = "";
for (int i = s.length() - 1; i >= 0; i--) {
a = a + s.charAt(i);
}
if (s.equals(a)) {
poli = true;
}
return poli;
}
}
Dynamic programming, similar to Longest Common Subsequence:
public static String LPL(String str, int i, int j, String result){
if(i > j) return result;
if(i == j)
return result.substring(0, result.length()/2) + str.charAt(i) + result.substring(result.length()/2);
if(str.charAt(i) == str.charAt(j))
return LPL(str, i+1, j-1, result.substring(0, length()/2 + str.charAt(i) + str.charAt(j) + result.substring(result.length()/2));
String str1 = LPL(str, i+1, j, "");
String str2 = LPL(str, i, j-1, "");
return (str1.length() > str2.length()) ? str1 : str2;
}
public static char[] getPalindromo(char str[], int start, int end)
{
// The only Exception I have found is with letters with acent like ába will not be a palindrome
while( start >= 0 && end < str.length &&
(toLowerCase(str[start]) == toLowerCase(str[end]) ||
!isLetter(str[start]) ||
!isLetter(str[end])))
{
if(!isLetter(str[start]) && isLetter(str[end]))
start--;
else if(isLetter(str[start]) && !isLetter(str[end]))
end++;
else{
start--;
end++;
}
}
start++;
end--;
return subString(str,start, (end-start)+1);
}
public static boolean isLetter(char c)
{
return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}
public static char toLowerCase(char c){
if(c >= 'a' && c <= 'z')
return c;
else return (char)(c + ('a'-'A'));
}
public static char[] subString(char str[],int from, int length){
char result [] = new char[length];
for(int index = 0; index < length; index++)
{
result[index] = str[from + index];
}
return result;
}
public static char[] getLongestPalindromo(char str[]){
if(str == null) return new char[0];
if(str.length < 2) return str;
char longestSoFar [] = new char[1];
longestSoFar[0] = str[0]; // default
char result[] = longestSoFar;
for(int i = 0; i < str.length; i++){
char palindromo[] = getPalindromo(str,i,i);
if(longestSoFar.length < palindromo.length)
longestSoFar = palindromo;
palindromo = getPalindromo(str,i,i+1);
if(longestSoFar.length < palindromo.length)
longestSoFar = palindromo;
if(result.length < longestSoFar.length)
result = longestSoFar;
}
return result;
}
public static void main(String [] args){
System.out.println(Amazon.getLongestPalindromo("123 Are we not drawn onward to new era? XXX".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A car, a man, a maraca.".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A dog, a plan, a canal: pagoda.".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal-Panama!".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A Santa dog lived as a devil God at NASA.".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A Toyota! Race fast, safe car! A Toyota!".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("Are we not pure? “No sir!” Panama’s moody Noriega brags. “It is garbage!” Irony dooms a man; a prisoner up to new era.".toCharArray()));
}
Output:
mafafito@mafafito-Aspire-4752:~/programming$ java Amazon
123 Are we not drawn onward to new era?
A car, a man, a maraca
A dog, a plan, a canal: pagoda
A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal-Panama
A Santa dog lived as a devil God at NASA
A Toyota! Race fast, safe car! A Toyota
Are we not pure? “No sir!” Panama’s moody Noriega brags. “It is garbage!” Irony dooms a man; a prisoner up to new era
mafafito@mafafito-Aspire-4752:~/programming$
// In swift
func longestPlainDrome(word: String) {
var charsInfo = [Character: Int]()
let chars = Array(word.lowercased().characters)
for char in chars {
if let count = charsInfo[char] {
charsInfo[char] = count + 1
} else {
charsInfo[char] = 1
}
}
var unpairedChars = [Character]()
var longestPlainChar = [Character]()
for (key, value) in charsInfo {
var repeatCount = value - 1
if repeatCount == 0 {
unpairedChars.append(key)
}
if value % 2 == 0 {
repeatCount = value
} else if value - 1 != 0 {
repeatCount = value - 1
unpairedChars.append(key)
}
for _ in 0..<repeatCount {
let index = ceil(Double(longestPlainChar.count/2))
longestPlainChar.insert(key, at: Int(index))
}
}
if let fistChar = unpairedChars.first {
let index = ceil(Double(longestPlainChar.count/2))
longestPlainChar.insert(fistChar, at: Int(index))
}
print(String(longestPlainChar))
}
func longestPlainDrome(word: String) {
var charsInfo = [Character: Int]()
let chars = Array(word.lowercased().characters)
for char in chars {
if let count = charsInfo[char] {
charsInfo[char] = count + 1
} else {
charsInfo[char] = 1
}
}
var unpairedChars = [Character]()
var longestPlainChar = [Character]()
for (key, value) in charsInfo {
var repeatCount = value - 1
if repeatCount == 0 {
unpairedChars.append(key)
}
if value % 2 == 0 {
repeatCount = value
} else if value - 1 != 0 {
repeatCount = value - 1
unpairedChars.append(key)
}
for _ in 0..<repeatCount {
let index = ceil(Double(longestPlainChar.count/2))
longestPlainChar.insert(key, at: Int(index))
}
}
if let fistChar = unpairedChars.first {
let index = ceil(Double(longestPlainChar.count/2))
longestPlainChar.insert(fistChar, at: Int(index))
}
print(String(longestPlainChar))
}
class LongestPal
{
public static void main(String[] args)
{
String s = "HYTTB";
String s1 = "";
String s2 = "";
String longPal = "";
for(int i = 0; i < s.length(); i++)
{
for(int j = i; j < s.length(); j++)
{
s1 = s1 + s.charAt(j);
s2 = rev(s1);
longPal = s2.equals(s1) && s2.length() >= longPal.length() ? (s2.compareTo(longPal) > 1 ? s2 : longPal) : longPal;
}
s1 = "";
}
System.out.println(longPal.length() > 1 ? "Longest Palindrome is = " + longPal : "Not Found");
}
public static String rev(String s1)
{
String s2 = "";
for(int i = 0; i < s1.length(); i++)
s2 = s1.charAt(i) + s2;
return s2;
}
}
/*
---------- run ----------
Longest Palindrome is = AAJKJAA
Output completed (0 sec consumed) - Normal Termination*/
class LongestPal
{
public static void main(String[] args)
{
String s = "HYTTB";
String s1 = "";
String s2 = "";
String longPal = "";
for(int i = 0; i < s.length(); i++)
{
for(int j = i; j < s.length(); j++)
{
s1 = s1 + s.charAt(j);
s2 = rev(s1);
longPal = s2.equals(s1) && s2.length() >= longPal.length() ? (s2.compareTo(longPal) > 1 ? s2 : longPal) : longPal;
}
s1 = "";
}
System.out.println(longPal.length() > 1 ? "Longest Palindrome is = " + longPal : "Not Found");
}
public static String rev(String s1)
{
String s2 = "";
for(int i = 0; i < s1.length(); i++)
s2 = s1.charAt(i) + s2;
return s2;
}
}
/*
---------- run ----------
Longest Palindrome is = AAJKJAA
Output completed (0 sec consumed) - Normal Termination*/
class LongestPal
{
public static void main(String[] args)
{
String s = "HYTTBOPOIYUIUY";
String s1 = "";
String s2 = "";
String longPal = "";
for(int i = 0; i < s.length(); i++)
{
for(int j = i; j < s.length(); j++)
{
s1 = s1 + s.charAt(j);
s2 = rev(s1);
longPal = s2.equals(s1) && s2.length() >= longPal.length() ? (s2.compareTo(longPal) > 1 ? s2 : longPal) : longPal;
}
s1 = "";
}
System.out.println(longPal.length() > 1 ? "Longest Palindrome is = " + longPal : "Not Found");
}
public static String rev(String s1)
{
String s2 = "";
for(int i = 0; i < s1.length(); i++)
s2 = s1.charAt(i) + s2;
return s2;
}
}
/*
---------- run ----------
Longest Palindrome is = YUIUY
Output completed (0 sec consumed) - Normal Termination*/
h<Tee><Tee>p://stevekrenzel.com/articles/longest-palnidrome
- whizz.comp March 14, 2012