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

- Ludovic Trottier January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer in C#-

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
                    {
                        charOccurance.Add(input[i], 1);
                    }
                }
                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");
                }
                    Console.ReadLine();                               
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                Console.ReadLine();
            }

- Mallikarjun Birajdar September 01, 2016 | Flag Reply
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..");
        }

- AD September 01, 2016 | Flag Reply
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..");
        }

- AD September 01, 2016 | Flag Reply
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..");
        }

- AD September 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve this using Manachar Algo.

- Anon September 01, 2016 | Flag Reply
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
			dict.Add(c,1);
		
		if (dict[c] % 2 == 0)
			length += 2;
	}
	
	if (length < s.Length)
		length++;
	
	return length;
}

- hnatsu September 05, 2016 | Flag Reply
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).

- funktional September 11, 2016 | Flag Reply
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).

- sergey.a.kabanov September 18, 2016 | Flag Reply
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);
	}

- Anonymous September 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

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

- ludovic.trottier.1 January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bhjsbdj

- Anonymous July 21, 2017 | Flag Reply
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..");
        }

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

- nil12285 September 08, 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