Amazon Interview Question SDETs
Country: United States
Interview Type: Written Test
Sure you can - O(N). But nobody's gonna expect you to do this in an interview. Even if you do, they'd know that you didn't figure this out but remember it.
Better (not in complexity sense) and simpler O(N2) algo: expand around 2N - 1 point of symmetries possible in a string for any palindrome and find the max size out of them.
Can any one tell how much time complexity for this program
public class Palindrome {
public boolean isPalindrome(String str){
int len = str.length();
boolean palindrome = true;
for(int i=0;i<len/2;i++){
if(str.charAt(i) != str.charAt(len-1-i)){
palindrome = false;
break;
}
}
return palindrome;
}
public boolean checkPalindrome(int start,int end,int len,String fullStr){
if(end > fullStr.length() ){return false;}
String subStr = fullStr.substring(start,end);
System.out.println(subStr);
if(isPalindrome(subStr)){
System.out.println("Biggest polindrome:"+subStr);
return true;
}
start++;end++;
return checkPalindrome(start,end,len,fullStr);
}
public static void main(String args[]){
Palindrome ob = new Palindrome();
String fullStr = "vallasssaaalav";
int len = fullStr.length();
for(int j=len;j>0;j--){
if(ob.checkPalindrome(0,j,j,fullStr)){
break;
}
}
}
}
Not sure what the hashmap has to do with this, but here's my stab:
import java.util.regex.Pattern;
import java.util.regex.Matcher;
public class Palindrome {
static void process(String target) {
String longest = "";
for (int i = 0; i < target.length(); i++) {
String check = target.substring(i);
for (int pos = 0; pos < (check.length() / 2) + 1; pos++) {
String part = check.substring(0, pos);
String regex = part + ".?" + new StringBuilder(part).reverse().toString();
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(check);
if (matcher.find()) {
String word = matcher.group();
if (word.length() > longest.length()) {
longest = word;
}
}
}
}
System.out.println(longest);
}
public static void main(String [] args) {
process("trtrracecaropop");
}
}
My O(N^2) solution:
public class LongestPalindrome {
public String find(String s) {
if (s == null || s.length() < 2) {
return s;
}
int maxLength = 0;
int start = 0;
for (int center = 0; center < s.length() - 1; ++center) {
int length = Math.max(findPalindromeLength(s, center), findPalindromeLength(s, center, center + 1));
if (length > maxLength) {
maxLength = length;
start = center - maxLength / 2;
if (maxLength % 2 == 0) {
start += 1;
}
}
}
return s.substring(start, start + maxLength);
}
private int findPalindromeLength(String s, int center) {
int length = 1;
return length + findPalindromeLength(s, center - 1, center + 1);
}
private int findPalindromeLength(String s, int i1, int i2) {
int length = 0;
while (i1 >= 0 && i2 < s.length() && s.charAt(i1) == s.charAt(i2)) {
length += 2;
--i1;
++i2;
}
return length;
}
}
I want to mention that there exists more sophisticated O(N) solution called "Manacher".
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class LargestPallindrom1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str2=sc.next();
LinkedHashMap lhs=new LinkedHashMap();
for(int i=1;i<str2.length();i++)
{
String str=str2.substring(0, i);
StringBuilder str1=new StringBuilder(str);
StringBuilder str3=str1.reverse();
String str4= new String(str3);
if(str4.equals(str))
{
int l=str.length();
lhs.put(str, l);
}
}
Set set3=lhs.entrySet();
Iterator it=set3.iterator();
int c=0;
int max=0;
while(it.hasNext())
{
Map.Entry entry=(Map.Entry)it.next();
c++;
if(c==1)
{
max=(Integer)entry.getValue();
}
else
{
int temp=(Integer)entry.getValue();
if(max<temp)
{
max=temp;
}
}
}
Iterator it2=set3.iterator();
while(it2.hasNext())
{
Map.Entry entry =(Map.Entry)it2.next();
int temp=(Integer)entry.getValue();
if(temp==max)
{
System.out.println(entry.getKey());
}
}
}
}
It seems mine is O(N*Log(N)) time and space. (maybe I am mistaken)
In Python, dict is a hash table.
map={}
count=0
def palindrom(str, x, y):
global count
global map
key = str[x:y+1]
if key in map.keys():
return map[key];
#print "check str=", key
for i in range(0, (y-x+1)//2):
count += 1
if str[i+x] != str[y - i]:
map[key] = ""
return ""
map[key] = key
return key
def max_pal(str):
max_substr =str[0]
len0 = len(str)
if len0 <= 1:
return str;
if len0 == 2:
if str[0] == str[1]:
return str
else:
return str[0]
for i in range(1, len0-1):
max_slen = (len0+1)//2
slen = i if (i+1) <= max_slen else (len0 - i -1)
for x in range(1, slen+1):
if x == 1 and len(max_substr) < 2:
if str[i-1] == str[i]:
max_substr = str[i-1:i+1]
elif str[i] == str[i+1]:
max_substr = str[i:i+2]
substr = palindrom(str, i-x, i+x)
if len(substr) > len(max_substr):
max_substr = substr
if i < max_slen :
substr = palindrom(str, i-x, i+x+1)
else:
substr = palindrom(str, i-x-1, i+x)
if len(substr) > len(max_substr):
max_substr = substr
print "str=", str, "len(str)=", len(str), "count=", count, "len(map)=", len(map), "max_substr=", max_substr
return max_substr
count=0;map={}; max_pal("aab")
count=0;map={}; max_pal("aba")
count=0;map={}; max_pal("abaabaaba")
count=0;map={}; max_pal("123456789987654321")
count=0;map={}; max_pal("12345678987654321")
count=0;map={}; max_pal("123456abcdefghijklmnopqrstuvwxyz")
count=0;map={}; max_pal("trtrracecaropop")
count=0;map={}; max_pal("123456789")
It seems to me mine is O(N*LogN) is time and space (maybe I am mistaken)
dict in python is hashmap
map={}
count=0
def palindrom(str, x, y):
global count
global map
key = str[x:y+1]
if key in map.keys():
return map[key];
#print "check str=", key
for i in range(0, (y-x+1)//2):
count += 1
if str[i+x] != str[y - i]:
map[key] = ""
return ""
map[key] = key
return key
def max_pal(str):
max_substr =str[0]
len0 = len(str)
if len0 <= 1:
return str;
if len0 == 2:
if str[0] == str[1]:
return str
else:
return str[0]
for i in range(1, len0-1):
max_slen = (len0+1)//2
slen = i if (i+1) <= max_slen else (len0 - i -1)
for x in range(1, slen+1):
if x == 1 and len(max_substr) < 2:
if str[i-1] == str[i]:
max_substr = str[i-1:i+1]
elif str[i] == str[i+1]:
max_substr = str[i:i+2]
substr = palindrom(str, i-x, i+x)
if len(substr) > len(max_substr):
max_substr = substr
if i < max_slen :
substr = palindrom(str, i-x, i+x+1)
else:
substr = palindrom(str, i-x-1, i+x)
if len(substr) > len(max_substr):
max_substr = substr
print "str=", str, "len(str)=", len(str), "count=", count, "len(map)=", len(map), "max_substr=", max_substr
return max_substr
count=0;map={}; max_pal("aab")
count=0;map={}; max_pal("aba")
count=0;map={}; max_pal("abaabaaba")
count=0;map={}; max_pal("123456789987654321")
count=0;map={}; max_pal("12345678987654321")
count=0;map={}; max_pal("123456abcdefghijklmnopqrstuvwxyz")
count=0;map={}; max_pal("trtrracecaropop")
count=0;map={}; max_pal("123456789")
Sorry about the duplicate post.
The output for the python proc is below:
str= aab len(str)= 3 count= 1 len(map)= 1 max_substr= aa
str= aba len(str)= 3 count= 1 len(map)= 1 max_substr= aba
str= abaabaaba len(str)= 9 count= 31 len(map)= 18 max_substr= abaabaaba
str= 123456789987654321 len(str)= 18 count= 172 len(map)= 136 max_substr= 123456789987654321
str= 12345678987654321 len(str)= 17 count= 148 len(map)= 120 max_substr= 12345678987654321
str= 123456abcdefghijklmnopqrstuvwxyz len(str)= 32 count= 465 len(map)= 465 max_substr= 1
str= trtrracecaropop len(str)= 15 count= 97 len(map)= 91 max_substr= racecar
str= 123456789 len(str)= 9 count= 28 len(map)= 28 max_substr= 1
C++ logic to display the list of palindromes in a main string.... using vector STL....
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//abcdabba
int main()
{
string str = "abcdabba";
vector<char> mvec;
copy( str.begin(), str.end(), back_inserter(mvec));//Converting string to vector.
//vector<char> mvec = {'a','b','b','a','c'};
vector<char>::iterator itrb = mvec.begin();
vector<char>::iterator itre = mvec.end();
cout<<"Main String\n" << str;
int ii = 0 ;
while(itrb != itre)
{
vector<char> tmp(itrb, itre);
int i = 0;
while(i < tmp.size())
{
vector<char> tmp1(tmp.begin(), (tmp.end()-i));
vector<char> tmp2 = tmp1;
if(tmp1.size() == 1)
break;
reverse(tmp2.begin(), tmp2.end());
if(tmp1 == tmp2)
{
cout<<"\n\nBelow string is a palindrome\n";
string s(tmp1.begin(), tmp1.end());
cout<<s;
break;
}
else
i++;
}
itrb++;
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//abcdabba
int main()
{
string str = "abcdabba";
vector<char> mvec;
copy( str.begin(), str.end(), back_inserter(mvec));//Converting string to vector.
//vector<char> mvec = {'a','b','b','a','c'};
vector<char>::iterator itrb = mvec.begin();
vector<char>::iterator itre = mvec.end();
cout<<"Main String\n" << str;
int ii = 0 ;
while(itrb != itre)
{
vector<char> tmp(itrb, itre);
int i = 0;
while(i < tmp.size())
{
vector<char> tmp1(tmp.begin(), (tmp.end()-i));
vector<char> tmp2 = tmp1;
if(tmp1.size() == 1)
break;
reverse(tmp2.begin(), tmp2.end());
if(tmp1 == tmp2)
{
cout<<"\n\nBelow string is a palindrome\n";
string s(tmp1.begin(), tmp1.end());
cout<<s;
break;
}
else
i++;
}
itrb++;
}
return 0;
}
#include <iostream>
#include <string>
std::string findLongestPalindrome(std::string s) {
int low, high, start, end;
bool palindromic;
std::string palindrome;
low = 0;
high = 0;
start = 0;
end = 0;
palindromic = false;
if (s.length() <= 1) {
return s;
}
for (int i = 1; i < s.length(); i++) {
low = i - 1;
high = i;
while (low >= 0 && high < s.length() && s[low] == s[high]) {
if ((high - low) > (end - start)) {
start = low;
end = high;
palindromic = true;
}
--low;
++high;
}
low = i - 1;
high = i + 1;
while (low >= 0 && high < s.length() && s[low] == s[high]) {
if ((high - low) > (end - start)) {
start = low;
end = high;
palindromic = true;
}
--low;
++high;
}
}
if (palindromic == true) {
palindrome = s.substr(start, end - start + 1);
}
return palindrome;
}
int main(int argc, const char * argv[]) {
std::cout << "Longest palindrome string is: " << findLongestPalindrome("abadd") << std::endl;
return 0;
}
{{public static String findLargestPalindrome(String input) {
String largestPalindrome = "";
for (int i = 0; i < input.length(); i++) {
// Stop looking because if there is another palindrome is wont be bigger than our largest
if (input.length() - i < largestPalindrome.length()) {
return largestPalindrome;
}
for (int j = input.length(); j > i; j--) {
if (isPalindrome(input.substring(i, j))
&& input.substring(i, j).length() > largestPalindrome.length()) {
largestPalindrome = input.substring(i, j);
}
}
}
return largestPalindrome;
}
public static boolean isPalindrome(String input) {
for (int i = 0, j = input.length() - 1; i <= j; i++, j--) {
if (input.charAt(i) != input.charAt(j)) {
return false;
}
}
return true;
}}}}
1. max possible longest palindrome's length is max even number closest to input's length
2. iterate through all input's sub-strings of length == max possible length
3. if candidate sub-string is palindrome - return it
4. decrement max possible length by 2 (it can only be even) and repeat steps 2-3
public class LongestPalindrome {
public String findLongestPalindrome(String input) {
if (input == null || input.length() == 1) {
return input;
}
// get maximum possible palindrome's length - always even
int palindromeLength = (input.length() % 2 == 0) ? input.length() : input.length() - 1;
while (palindromeLength > 0) {
// iterate all substrings with length == palindromeLength
for (int i = 0, j = palindromeLength; j <= input.length(); i++, j++) {
String candidate = input.substring(i, j);
if (isPalindrome(candidate)) {
return candidate; // longest substring palindrome
}
}
palindromeLength = palindromeLength - 2;
}
return input.substring(0, 1); // no palindromes with length >=2 - return first char
}
private boolean isPalindrome(String input) {
if (input == null || input.length() == 1) {
return true; // base palindrome
}
if (input.length() % 2 == 1) {
return false; // odd strings can NOT be palindromes
}
for (int i = 0, j = input.length() - 1; i < j; i++, j--) {
if (input.charAt(i) != input.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
LongestPalindrome test = new LongestPalindrome();
String input = "abccbbcca";
System.out.println(String.format("Longest palindrome from '%s' is '%s'", input, test.findLongestPalindrome(input)));
}
}
public class LongestPalindromeTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
longestPalindrome(s);
}
public static boolean isPalindrome(String str) {
int i = 0;
int j = str.length() - 1;
int flag = 0;
for(int k=0;k<str.length();k++) {
if(str.charAt(k)!=str.charAt(str.length()-1-k)) {
return false;
}
}
return true;
}
public static void longestPalindrome(String str) {
int i=0;
int j=str.length() - 1;
if(str.length()<=0) {
return;
}
if(isPalindrome(str)) {
System.out.println(str);
}
else {
if(str.charAt(i)!=str.charAt(j) && str.charAt(i+1)== str.charAt(j)) {
longestPalindrome(str.substring(1, str.length()));
} else if(str.charAt(i)!=str.charAt(j) && str.charAt(i)== str.charAt(j-1)) {
longestPalindrome(str.substring(0, j));
} else {
longestPalindrome(str.substring(1,j));
}
}
}
public class LongestPalindromeTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
longestPalindrome(s);
}
public static boolean isPalindrome(String str) {
int i = 0;
int j = str.length() - 1;
int flag = 0;
for(int k=0;k<str.length();k++) {
if(str.charAt(k)!=str.charAt(str.length()-1-k)) {
return false;
}
}
return true;
}
public static void longestPalindrome(String str) {
int i=0;
int j=str.length() - 1;
if(str.length()<=0) {
return;
}
if(isPalindrome(str)) {
System.out.println(str);
}
else {
if(str.charAt(i)!=str.charAt(j) && str.charAt(i+1)== str.charAt(j)) {
longestPalindrome(str.substring(1, str.length()));
} else if(str.charAt(i)!=str.charAt(j) && str.charAt(i)== str.charAt(j-1)) {
longestPalindrome(str.substring(0, j));
} else {
longestPalindrome(str.substring(1,j));
}
}
}
public class LongestPalindromeTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
longestPalindrome(s);
}
public static boolean isPalindrome(String str) {
int i = 0;
int j = str.length() - 1;
int flag = 0;
for(int k=0;k<str.length();k++) {
if(str.charAt(k)!=str.charAt(str.length()-1-k)) {
return false;
}
}
return true;
}
public static void longestPalindrome(String str) {
int i=0;
int j=str.length() - 1;
if(str.length()<=0) {
return;
}
if(isPalindrome(str)) {
System.out.println(str);
}
else {
if(str.charAt(i)!=str.charAt(j) && str.charAt(i+1)== str.charAt(j)) {
longestPalindrome(str.substring(1, str.length()));
} else if(str.charAt(i)!=str.charAt(j) && str.charAt(i)== str.charAt(j-1)) {
longestPalindrome(str.substring(0, j));
} else {
longestPalindrome(str.substring(1,j));
}
}
}
public class LargestPalindromString {
public static boolean palindrome(String temp){
//System.out.println(temp);
if(temp.length()==2){
if(temp.charAt(0)==temp.charAt(1))
return true;
else
return false;
}
//System.out.println(temp.length()/2);
for(int i=0;i<temp.length()/2;i++){
if(temp.charAt(i)!=temp.charAt(temp.length()-i-1)){
return false;
}
}
return true;
}
public static void main(String args[]){
String str="jkashshkhsd";
int longest=1;
for(int i=2;i<str.length();i++){
for(int j=0;j<str.length()-i;j++){
if(palindrome(str.substring(j, j+i))){
longest=i;
System.out.println(str.substring(j, j+i));
}
}
}
System.out.println("Largest Palindrome: "+longest);
}
}
package com.learn;
import java.util.*;
public class Palindrome {
public static void main(String[] args){
Hashtable<Character,Integer> ht = new Hashtable<Character,Integer>();
Scanner sc = new Scanner(System.in);
boolean flagVal1, flagVal2;
String str, temp1, temp2;
temp1 = "";
temp2 = "";
flagVal1 = false;
flagVal2 = false;
int x=0;
String cetreVal;
cetreVal = "";
str = sc.next();
x = str.length();
for (int i = 0; i < x; i++){
char c = str.charAt(i);
boolean bln;
bln = ht.containsKey(c);
if(!bln)
ht.put(c, 1);
else
ht.put(c, ht.get(c)+1);
}
System.out.println(ht);
Set<Character> keys = ht.keySet();
for(Character key: keys){
System.out.println("Value of "+key+" is: "+ht.get(key));
if(ht.get(key) > 1){
int div = ht.get(key) / 2;
int mod = ht.get(key) % 2;
for (int j = 0; j <div;j++){
temp1 = temp1 + key;
temp2 = key + temp2;
}
if (mod == 1){
cetreVal = key.toString();
}
}
else if(ht.get(key) == 1)
cetreVal = key.toString();
}
temp1 = temp1 +cetreVal +temp2;
System.out.println("String is=" +temp1);
}
}
Use manacher algorithm
- Vladimir October 01, 2015