Amazon Interview Question
Quality Assurance EngineersTeam: Kindle
Country: India
Interview Type: In-Person
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();
}
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..");
}
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..");
}
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..");
}
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;
}
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).
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).
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);
}
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);
}
}
}
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..");
}
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)
A python solution
- Ludovic Trottier January 14, 2017