## Amazon Interview Question for Quality Assurance Engineers

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

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

A python solution

``````def max_palindrone_length(str):
abc = {}
for character in str:
count = abc.setdefault(character, 0)
abc[character] = count + 1

freq = 0
odd = 0
for key, value in abc.items():
freq = freq + value - (value % 2)
if value % 2 == 1:
odd = 1

return freq + odd``````

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

``````try
{
//Find the length of string having pallindrome, u can remove any character and shuffle it
string input = "abb";
Dictionary<char, int> charOccurance = new Dictionary<char, int>();
int count = 0;
bool isPalindrome=false;
bool isOdd = false;
for (int i = 0; i < input.Length; i++)
{
if (charOccurance.ContainsKey(input[i]))
{
charOccurance[input[i]] += 1;
}
else
{
}
}
foreach (int value in charOccurance.Values)
{
if (value % 2 == 0)
{
count = count + value;
}
if (value % 2 != 0)
{
count = count + value - 1;
isOdd = true;
}
if (isPalindrome == false)
{
if(value>1)
isPalindrome = true;
}
}
if (isPalindrome == true)
{
if (isOdd)
{
Console.WriteLine("Length of string={0}", count + 1);
}
else
{
Console.WriteLine("Length of string={0}", count);
}
}
else
{
Console.WriteLine("Not a single palindrome possible");
}
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}``````

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

``````String ip = "ajandfbakrbla";
String[] ipArr = ip.split("");
Map<String, Integer> charFreqStMap = new HashMap<String, Integer>();

Integer maxPal = 0;
for(int i = 1; i < ip.length(); i++) {
String a = ipArr[i];
if(charFreqStMap.containsKey(a)) {
Integer prevCount = charFreqStMap.get(a);
charFreqStMap.put(a, prevCount + 1);
if(maxPal < prevCount + 1) {
maxPal = prevCount + 1;
}
} else {
charFreqStMap.put(a, 1);
}
}
if(maxPal > 0) {
System.out.println("Max Length Palindrome String is: " + ++maxPal);
} else {
System.out.println("Palindrome not present in input string..");
}``````

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

``````String ip = "ajandfbakrbla";
String[] ipArr = ip.split("");
Map<String, Integer> charFreqStMap = new HashMap<String, Integer>();

Integer maxPal = 0;
for(int i = 1; i < ip.length(); i++) {
String a = ipArr[i];
if(charFreqStMap.containsKey(a)) {
Integer prevCount = charFreqStMap.get(a);
charFreqStMap.put(a, prevCount + 1);
if(maxPal < prevCount + 1) {
maxPal = prevCount + 1;
}
} else {
charFreqStMap.put(a, 1);
}
}
if(maxPal > 0) {
System.out.println("Max Length Palindrome String is: " + ++maxPal);
} else {
System.out.println("Palindrome not present in input string..");
}``````

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

``````String ip = "ajandfbakrbla";
String[] ipArr = ip.split("");
Map<String, Integer> charFreqStMap = new HashMap<String, Integer>();

Integer maxPal = 0;
for(int i = 1; i < ip.length(); i++) {
String a = ipArr[i];
if(charFreqStMap.containsKey(a)) {
Integer prevCount = charFreqStMap.get(a);
charFreqStMap.put(a, prevCount + 1);
if(maxPal < prevCount + 1) {
maxPal = prevCount + 1;
}
} else {
charFreqStMap.put(a, 1);
}
}
if(maxPal > 0) {
System.out.println("Max Length Palindrome String is: " + ++maxPal);
} else {
System.out.println("Palindrome not present in input string..");
}``````

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

We can solve this using Manachar Algo.

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

C# implementation, O(n) just count the number of characters

``````public static int GetMaxPalindromeLength(string s)
{
if (string.IsNullOrEmpty(s))
return 0;

int length = 0;
var dict = new Dictionary<char, int>();
foreach (var ch in s)
{
var c = ch;
if (c >= 'A' && c <= 'Z')
c = (char)(c - 'A');

if(dict.ContainsKey(c))
dict[c]++;
else

if (dict[c] % 2 == 0)
length += 2;
}

if (length < s.Length)
length++;

return length;
}``````

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

If I read the problem correctly, if you can shuffle and/or remove characters, then the longest palindrome is the sum of all of the even count chars and the longest odd count char (if there is one).

``````public static int maxLengthPalindrome(String s) {
String[] sArr = s.split("");
Map<String, Integer> charFreq = new HashMap<String, Integer>();

for (int i = 0; i < s.length(); i++) {
String c = sArr[i];
if (charFreq.containsKey(c)) {
int count = charFreq.get(c);
charFreq.put(c, count + 1);
} else {
charFreq.put(c, 1);
}
}

int maxPal = 0;
int maxOdd = 0;
for (String c : charFreq.keySet()) {
int count = charFreq.get(c);
if (count % 2 == 0) {
maxPal += count;
} else if (count > maxOdd) {
maxOdd = count;
}
}
return maxPal + maxOdd;
}``````

First pass creates the frequency map and is O(n) where n is length of string. Second pass adds up the frequency map and is O(k) where k is the number of keys. Generally k will be bounded by both n and max of the character set, so in practice O(kn) should reduce to O(n).

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

The idea is simple:

1). Make an array of 256 number (each index represents the character).
Go through the string, add the number at the index, when we have such character.

2). Take all characters that are in our string even number of times, plus the very first character that we have only once (it can be the middle character in the palindrome).

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

``````public static void main(String[] args) {

String ip = "abcabcbcdsa";
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < ip.length(); i++) {
if (map.containsKey(ip.charAt(i))) {
map.put(ip.charAt(i), map.get(ip.charAt(i)) + 1);
} else {

map.put(ip.charAt(i), 1);
}
}
boolean flag = false;
int totLen = 0;
Iterator<Entry<Character, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Entry<Character, Integer> val = it.next();
if (val.getValue() % 2 == 1) {
totLen += val.getValue() - 1;
flag = true;
} else {
totLen += val.getValue();
}
}
if (flag) {
totLen++;
}
System.out.println(totLen);
}``````

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

A python solution.

``````def max_palindrone_length(str):
abc = {}
for character in str:
count = abc.setdefault(character, 0)
abc[character] = count + 1

freq = 0
odd = 0
for key, value in abc.items():
freq = freq + value - (value % 2)
if value % 2 == 1:
odd = 1

return freq + odd``````

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

``bhjsbdj``

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

``````String ip = "ajandfbakrbla";
String[] ipArr = ip.split("");
Map<String, Integer> charFreqStMap = new HashMap<String, Integer>();

Integer maxPal = 0;
for(int i = 1; i < ip.length(); i++) {
String a = ipArr[i];
if(charFreqStMap.containsKey(a)) {
Integer prevCount = charFreqStMap.get(a);
charFreqStMap.put(a, prevCount + 1);
if(maxPal < prevCount + 1) {
maxPal = prevCount + 1;
}
} else {
charFreqStMap.put(a, 1);
}
}
if(maxPal > 0) {
System.out.println("Max Length Palindrome String is: " + ++maxPal);
} else {
System.out.println("Palindrome not present in input string..");
}``````

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

I think there is much easy solution
find the frequency of the element
and then based on the frequency you can find the longest possible palindrome with given string

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

if not s:
return 0

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)

return pl``````

space : o(n)
time : sort => O(n)

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.