Amazon Interview Question
Quality Assurance EngineersTeam: Kindle
Country: India
Interview Type: In-Person
A different approach
private int maxPalindromeLength(String input) {
int letters = 0;
int length = 0;
for (int i = 0; i < input.length(); i++) {
int move = input.charAt(i) - 97;
if (((letters >>> move) & 1) == 1) {
letters -= (1 << move);
length += 2;
} else {
letters |= (1 << move);
}
}
return length + (letters != 0 ? 1 : 0);
}
public class LongestPalindrom {
public static void main(String[] args) {
LongestPalindrom longest = new LongestPalindrom();
System.out.println(longest.longest("aabcbcbdcc"));
}
public String longest(String string) {
if (string.length() == 0 || string == null) {
return "";
}
StringBuffer palindrom = new StringBuffer();
Map<Character, Integer> charBag = new HashMap<Character, Integer>();
for (Character c : string.toCharArray()) {
int totalChar = charBag.get(c) != null ? charBag.get(c) : 0;
if ((totalChar + 1) % 2 == 0) {
palindrom.append(c);
palindrom = palindrom.insert(0, c);
charBag.remove(c);
continue;
}
charBag.put(c, ++totalChar);
}
if (charBag.size() > 0) {
Iterator it = charBag.entrySet().iterator();
Map.Entry pair = (Map.Entry<Character, Integer>)it.next();
String c = pair.getKey().toString();
palindrom.insert(palindrom.length()/2, c);
}
return palindrom.toString();
}
}
With Complexity equivalent to O(n)
private static int getMaxLength(String next) {
Map<Character, Integer> map = new ConcurrentHashMap<Character, Integer>();
int count = 1;
char key = '0', mid = '0';
int val;
String palin = "";
for (Character ch : next.toCharArray()) {
if (map.containsKey(ch)) {
count = map.get(ch) + 1;
map.put(ch, count);
} else {
map.put(ch, 1);
}
}
System.out.println(map);
while (! map.isEmpty())
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2) {
val = entry.getValue();
key = entry.getKey();
palin = palin + key;
map.put(key, val - 2);
} else {
if (entry.getValue() == 1)
mid = entry.getKey();
map.remove(entry.getKey());
continue;
}
}
if (mid != '0')
palin = palin + mid + reverse(palin);
else
palin = palin + reverse(palin);
System.out.println("Palin is : " + palin);
return palin.length();
}
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);
}
}
import java.util.*;
public class findAllPalindromeMine {
public static void main(String[] args) {
Set<String> palstr = new HashSet<String>(subpal("abcacbbbca"));
int len=0;
len = findlongpal(palstr);
printpal(palstr,len);
}
public static Set<String> subpal(String str)
{
String temp="";
int count = 2;
Set<String> palary = new HashSet<String>();
for(int i=0;i<str.length();i++)
{
for(int j=0;j<=count+j;j++)
{
if(count+j>=str.length()){
break;
}
temp = str.substring(j,count+j);
if (temp.equals(new StringBuilder(temp).reverse().toString()))
{
palary.add(temp);
}
}
count++;
}
return palary;
}
public static int findlongpal(Set<String> pal)
{
int len=0;
for(String s: pal)
{
if(len<s.length())
len=s.length();
}
return len;
}
public static void printpal(Set<String> pal,int len)
{
for(String s:pal)
{
if(s.length()>=len)
System.out.println(s);
}
}
}
import java.util.*;
public class findAllPalindromeMine {
public static void main(String[] args) {
Set<String> palstr = new HashSet<String>(subpal("abcacbbbca"));
int len=0;
len = findlongpal(palstr);
printpal(palstr,len);
}
public static Set<String> subpal(String str)
{
String temp="";
int count = 2;
Set<String> palary = new HashSet<String>();
for(int i=0;i<str.length();i++)
{
for(int j=0;j<=count+j;j++)
{
if(count+j>=str.length()){
break;
}
temp = str.substring(j,count+j);
if (temp.equals(new StringBuilder(temp).reverse().toString()))
{
palary.add(temp);
}
}
count++;
}
return palary;
}
public static int findlongpal(Set<String> pal)
{
int len=0;
for(String s: pal)
{
if(len<s.length())
len=s.length();
}
return len;
}
public static void printpal(Set<String> pal,int len)
{
for(String s:pal)
{
if(s.length()>=len)
System.out.println(s);
}
}
}
Here is my solution in Java:
package main;
import java.util.Map;
import java.util.HashMap;
public class longestPalindrome {
public static void main(String[] args) {
String word = "aabcbcb dcc";
String maxPalindrome = maxStringPalindrome(countCharacters(word));
System.out.println("The max string that forms palindrome is: " + maxPalindrome + " the lenght is: "
+ maxPalindrome.length());
maxPalindrome = new StringBuilder(maxPalindrome).reverse().toString();
System.out.println(maxPalindrome);
}
public static Map<Character, Integer> countCharacters(String word) {
Map<Character, Integer> data = new HashMap<Character, Integer>();
for (int i = 0; i <= word.length() - 1; i++) {
if (word.charAt(i) != ' ') {
char c = word.charAt(i);
if (data.containsKey(c)) {
data.put(c, data.get(c) + 1);
} else {
data.put(c, 1);
}
}
}
return data;
}
public static String maxStringPalindrome(Map<Character, Integer> data) {
String beginning = "";
char medium = ' ';
String end = "";
for (Map.Entry<Character, Integer> entry : data.entrySet()) {
if (entry.getValue() == 1) {
medium = entry.getKey();
}
if (entry.getValue() % 2 == 0) {
int count = 0;
while (count < entry.getValue() / 2) {
beginning = beginning + entry.getKey();
count++;
}
} else if (entry.getValue() % 2 == 1 && entry.getValue() > 1) {
int count = 0;
while (count < (entry.getValue() - 1) / 2) {
beginning = beginning + entry.getKey();
count++;
}
}
}
end = new StringBuilder(beginning).reverse().toString();
return beginning + medium + end;
}
int maxPalindrome(String s) {
if (s == null) return 0;
int len = s.length();
int max = 0;
Set <Character> set = new HashSet <Character> ();
for (int i=0; i<len; i++) {
if (set.contains(s.charAt(i))) {
max+=2;
set.remove(s.charAt(i));
} else {
set.add(s.charAt(i));
}
}
return set.size() > 0 ? max+1 : max;
}
import java.util.HashMap;
import java.util.Iterator;
public class Plaindrome {
static String str = "aabcbcbdcc";
static HashMap<String, Integer> charCount = new HashMap<>();
public static void main(String[] f){
String s = "";
charCount.put(str.substring(0, 1), 1);
int index = 1;
while(index < str.length()){
int count = charCount.get(str.substring(index,index+1))==null?0:charCount.get(str.substring(index,index+1)) + 1;
if(count == 2){
s = str.substring(index,index+1) + s + str.substring(index,index+1);
charCount.put(str.substring(index,index+1), 0);
}else{
charCount.put(str.substring(index,index+1), 1);
}
index ++;
}
Iterator<String> itr = charCount.keySet().iterator();
while(itr.hasNext()){
String e = itr.next();
Integer a = charCount.get(e);
if(a !=null && a==1 && s.length() % 2 ==0){
s = s.substring(0, (s.length())/2) + e + s.substring((s.length())/2,s.length());
break;
}
}
System.out.println(s);
}
}
import java.util.HashMap;
import java.util.Iterator;
public class Plaindrome {
static String str = "aabcbcbdcc";
static HashMap<String, Integer> charCount = new HashMap<>();
public static void main(String[] f){
String s = "";
charCount.put(str.substring(0, 1), 1);
int index = 1;
while(index < str.length()){
int count = charCount.get(str.substring(index,index+1))==null?0:charCount.get(str.substring(index,index+1)) + 1;
if(count == 2){
s = str.substring(index,index+1) + s + str.substring(index,index+1);
charCount.put(str.substring(index,index+1), 0);
}else{
charCount.put(str.substring(index,index+1), 1);
}
index ++;
}
Iterator<String> itr = charCount.keySet().iterator();
while(itr.hasNext()){
String e = itr.next();
Integer a = charCount.get(e);
if(a !=null && a==1 && s.length() % 2 ==0){
s = s.substring(0, (s.length())/2) + e + s.substring((s.length())/2,s.length());
break;
}
}
System.out.println(s);
}
}
String t="HELLO WORLD!";
HashMap<Character,Integer> m =new HashMap();
for(int i=0;i<t.length();i++)
{
if(!m.containsKey(t.charAt(i)))
m.put(t.charAt(i), 1);
else
m.put(t.charAt(i), m.get(t.charAt(i))+1);
}
int maxList = Collections.max(m.values());
for(Map.Entry<Character, Integer> d : m.entrySet())
{
if(d.getValue().equals(maxList))
{
System.out.println(d.getKey());
}
}
import java.util.HashMap;
import java.util.Map;
public class CountPallindrom {
public static void main(String[] args){
String c = "aabcbcbdcc";
char[] chars = c.toCharArray();
Map<Character,Integer> map =new HashMap<>();
for(char ch:chars){
if(!map.containsKey(ch)){
map.put(ch,1);
}else{
map.put(ch,map.get(ch)+1);
}
}
int maxEven = 0;
char maxChar = Character.MIN_VALUE;
for(char key:map.keySet()){
if((map.get(key) > maxEven) && (map.get(key)%2==0)){
maxEven = map.get(key);
maxChar = key;
}else if((map.get(key)%2 != 0) && map.get(key) > 1 ){
map.put(key,map.get(key)-1);
}
}
int sum = 0;
for(char key:map.keySet()){
sum =sum+map.get(key);
}
System.out.println(sum);
}
}
Two (similar) possible solutions
# A string is palindrome if it can be decomposed in three
# substrings: left_string, center_string, right_string
# where left_string equals right_string up to inverting
# the order of its elements, and center_string has at most
# length 1.
# If a charachter c appears 2*m+1 times in the input_string
# then c contributes to the lengt of the longest palindrome
# by 2*m (as we can put m times c in the left_string and
# and m times c in the right_string) or, if
# the center_string has not yet length 1, by 2*m+1
def length_longest_palindrome(input_string) :
hash_table = {}
length = 0
possible_centers = 0
position = 0
while(position < len(input_string)) :
current_char = input_string[position]
if current_char in hash_table :
n = hash_table[current_char]
if n % 2 == 0 :
possible_centers += 1
else:
length += 2
possible_centers -= 1
hash_table[current_char] = n + 1
else:
hash_table[current_char] = 1
possible_centers += 1
position += 1
return length + min(1, possible_centers)
def length_longest_palindrome_no_hash(a_string) :
l = 0
poss_cent = 0
help_string = []
pos = 0
while pos < len(a_string) :
cur_char = a_string[pos]
if cur_char in help_string :
help_string.remove(cur_char)
l += 2
poss_cent = max(0, poss_cent-1)
else :
help_string.append(cur_char)
poss_cent += 1
pos +=1
return l + min(1, poss_cent)
#test
print(length_longest_palindrome('asabbbccsd'))
print(length_longest_palindrome_no_hash('asabbbccsd'))
put every char into a hashset. If a char is already in the hashset, remove it. This way, after iterating over the string, we're left with a set of chars that occur an odd number of times in the original string. Since a palindrome has at most one character that may appear an odd number of times, the max possible length is s.length + 1 - hashset.numkeys. O(N) time O(N) space
public int maxPalindromeLength(string s){
HashSet<char> set = new HashSet<char>();
int n = s.length;
for(int i = 0; i < s.length; ++i){
if( set.ContainsKey(s[i]) ){
set.Remove(s[i]);
}else{
set.Add(s[i]);
}
}
return n + 1 - set.Count;
}
Seems that you only need to count all pairs and if there is at least one unpair then it can be added one as 'abcba' and 'abba' are both valid palindrome.
public int MaxPalindrome(string S)
{
var counts = new Dictionary<char, int>();
foreach(var s in S)
{
if(!counts.ContainsKey(s))
{
counts.Add(s, 1);
}
else
{
counts[s]++;
}
}
bool hasMiddle = false;
int total = 0;
foreach(var kvp in counts)
{
total+= kvp.Value / 2 * 2;
if(kvp.Value % 2 == 1)
hasMiddle = true;
}
if(hasMiddle)
total++;
return total;
}
Here's my take on the problem. Problem is simple. Count how many times each character occurred in the array. Count of characters occurring even time in the array can be simply added to max palindrome length. Count of odd occurring characters is added as count_of_odd - 1. If there was atleast 1 odd occurring character, then add 1 to the final length.
- Anonymous September 21, 2016