Snapdeal Interview Question
Senior Software Development EngineersCountry: India
import java.util.HashMap;
import java.util.Map.Entry;
public class NeeedtoMakePalindrome {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "aabbbccddee";
// if string is of even length then frequenecy of all chars should be
// even.
// if string is odd length than atmost one char can have odd frequency
// aabcc(correct, a palidrome can be made out of this pattern)
// aaabbef(not a palindrome)
HashMap<Character, Integer> hm = new HashMap<>();
int len = s.length();
for (char ch : s.toCharArray()) {
if (hm.containsKey(ch)) {
hm.put(ch, hm.get(ch) + 1);
} else {
hm.put(ch, 1);
}
}
HashMap<Character, Integer> paddingmap = new HashMap<>();
int totalpaddingneeded = 0;
if (len % 2 == 0) {
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;
if (value % 2 == 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}
if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}
} else {
System.out.println("Already palindrome can be construcuted");
}
}
else {
System.out.println("when length is odd");
int count = 0;
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;
if (value % 2 == 1) {
count++;
if (count >= 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}
}
if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}}}}}
import java.util.HashMap;
import java.util.Map.Entry;
public class NeeedtoMakePalindrome {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "aabbbccddee";
// if string is of even length then frequenecy of all chars should be
// even.
// if string is odd length than atmost one char can have odd frequency
// aabcc(correct, a palidrome can be made out of this pattern)
// aaabbef(not a palindrome)
HashMap<Character, Integer> hm = new HashMap<>();
int len = s.length();
for (char ch : s.toCharArray()) {
if (hm.containsKey(ch)) {
hm.put(ch, hm.get(ch) + 1);
} else {
hm.put(ch, 1);
}
}
HashMap<Character, Integer> paddingmap = new HashMap<>();
int totalpaddingneeded = 0;
if (len % 2 == 0) {
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;
if (value % 2 == 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}
if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}
} else {
System.out.println("Already palindrome can be construcuted");
}
}
else {
System.out.println("when length is odd");
int count = 0;
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;
if (value % 2 == 1) {
count++;
if (count >= 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}
}
if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}
}
}
}
}
O(len(s)^2) memory, runtime.
- emb June 22, 2016