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

- Anonymous September 21, 2016 | Flag Reply
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

- nil12285 September 21, 2016 | Flag Reply
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);
	}

- Motakjuq September 27, 2016 | Flag Reply
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();
	}
}

- ethioer September 29, 2016 | Flag Reply
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();

	}

- getPDat October 06, 2016 | Flag Reply
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);
}

}

- himanshutime@gmail.com October 11, 2016 | Flag Reply
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()))
{
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);
}
}
}

- Varoune Coumar December 25, 2016 | Flag Reply
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()))
{
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);
}
}
}

- Varoune Coumar December 25, 2016 | Flag Reply
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;
	}

- Anonymous January 15, 2017 | Flag Reply
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 {
			set.add(s.charAt(i));
		}
	}	
	return set.size() > 0 ? max+1 : max;
}

- Charan February 03, 2017 | Flag Reply
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);
        
    }
}

- Anonymous February 07, 2017 | Flag Reply
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);
        
    }
}

- Anonymous February 07, 2017 | Flag Reply
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

- Shweta Aggarwal July 10, 2018 | Flag Reply
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'))

- Luke Rhinehart September 18, 2016 | Flag Reply
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{
			set.Add(s[i]);	
		}
	}
	
	return n + 1 - set.Count;
}

- Anonymous September 18, 2016 | Flag Reply
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))
		{
			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;
}

- Nelson Perez September 18, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More