## Amazon Interview Question for Quality Assurance Engineers

Team: Kindle
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 5 vote

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.

``````// Example program
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int getIndex(char c)
{
return c - 'a';
}

unsigned int getMaxPalindromeLength(const string&  s)
{
if (s.length() == 0) return 0;

vector<unsigned int> indexes(26, 0);

for (unsigned int i = 0; i < s.length(); ++i)
{
indexes[getIndex(s[i])] += 1;
}

bool hasOdd = false;
int len = 0;

for (unsigned int i = 0; i < 26; ++i)
{
if (indexes[i]%2 == 1)
{
len += indexes[i] - 1;
}
else
{
len += indexes[i];
}
}

if (hasOdd) len += 1;

return len;
}

int main()
{
string s("aabcbcbdcc");

cout << getMaxPalindromeLength(s) << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def get_longest_palindrom_length(s):

if not s:
return 0
#Calculate Frequency of each char
sd = {}
for i in s:
if i not in sd:
sd[i] = 1
else:
sd[i] += 1

pl = 1
for i, c in sd.items():
if c > 1:
pl += ((c // 2) * 2)

return pl

s = 'aabcbcbdcc'
print(get_longest_palindrom_length(s))   #9``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 {
}
}
return set.size() > 0 ? max+1 : max;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

# Solution in Python
from collections import Counter

str='aabbcc'
wc=Counter(str)
print wc

odd=0
freq=0
for i in wc.values():
if i%2==0:
freq+=i
elif i%2==1:
freq+=i-1
odd=1
print freq+odd

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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'))``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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{
}
}

return n + 1 - set.Count;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}``````

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.

### 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.