Uber Interview Question Software Engineers
Country: United States
if the string length is even then each unique should be present even number of times. if length is odd then each character except 1 char should be present even number of times. if this condition is not satisfied then return -1 as we wont be able to form palindromic permutation.
Now get list of chars which appear 2 times. Get permutations for these unique chars. Now iterate through this permutation list, for each permutation string append its reverse to it. The resultant string would be a palindrome. add this to result list. do this for all.
If string was odd length then while appending reverse first append the char which is present only 1 time.
private Set<String> palindromes;
private HashMap<Character, Integer> map;
public static void buildPalindromes(String s) {
if(s == null || s.length() == 0) {
return;
}
palindromes = new HashSet<>();
int count;
HashMap<Character, Integer> map = new HashMap<>();
//fill the map
for(char c : s.toCharArray()) {
if(map.containsKey(c)) {
count = map.get(c);
map.put(c, ++count);
}
else {
map.put(c, 1);
}
}
//check if exist more than 1 character with odd frequency
count = 0;
for(Map.Entry<Character, Integer> set : map.entrySet()) {
if(set.getValue() % 2 == 1) {
count++;
if(count == 2) {
return;
}
}
}
buildPalindrome(new char[s.length()], 0);
}
private static void buildPalindrome(char[] sofar, int ind) {
//base condition
if(ind > sofar.length / 2) {
palindromes.add(new String(sofar));
return;
}
//if length of input is odd
if(ind == sofar.length - 1 - ind) {
Iterator<Map.Entry<Character, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Character, Integer> pair = it.next();
if(pair.getValue() > 0) {
sofar[ind] = pair.getKey();
palindromes.add(new String(sofar));
}
}
return;
}
Iterator<Map.Entry<Character, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Character, Integer> pair = it.next();
if(pair.getValue() < 2) {
continue;
}
sofar[ind] = sofar[sofar.length - 1 - ind] = pair.getKey();
pair.setValue(pair.getValue() - 2);
buildPalindrome(sofar, ind+1, map);
pair.setValue(pair.getValue() + 2);
}
}
private Set<String> palindromes;
private HashMap<Character, Integer> map;
public static void buildPalindromes(String s) {
if(s == null || s.length() == 0) {
return;
}
palindromes = new HashSet<>();
int count;
HashMap<Character, Integer> map = new HashMap<>();
//fill the map
for(char c : s.toCharArray()) {
if(map.containsKey(c)) {
count = map.get(c);
map.put(c, ++count);
}
else {
map.put(c, 1);
}
}
//check if exist more than 1 character with odd frequency
count = 0;
for(Map.Entry<Character, Integer> set : map.entrySet()) {
if(set.getValue() % 2 == 1) {
count++;
if(count == 2) {
return;
}
}
}
buildPalindrome(new char[s.length()], 0);
}
private static void buildPalindrome(char[] sofar, int ind) {
//base condition
if(ind > sofar.length / 2) {
palindromes.add(new String(sofar));
return;
}
//if length of input is odd
if(ind == sofar.length - 1 - ind) {
Iterator<Map.Entry<Character, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Character, Integer> pair = it.next();
if(pair.getValue() > 0) {
sofar[ind] = pair.getKey();
palindromes.add(new String(sofar));
}
}
return;
}
Iterator<Map.Entry<Character, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Character, Integer> pair = it.next();
if(pair.getValue() < 2) {
continue;
}
sofar[ind] = sofar[sofar.length - 1 - ind] = pair.getKey();
pair.setValue(pair.getValue() - 2);
buildPalindrome(sofar, ind+1, map);
pair.setValue(pair.getValue() + 2);
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
/**
* Created by dushyant.sabharwal on 11/20/16.
*/
public class GeneratePalindromicPermutations {
private static HashMap<String, Integer> unique_permutations = new HashMap<>();
private static String unique_chars = "";
public static void main(String []args) {
System.out.println("Enter the string for checking");
Scanner sc = new Scanner(System.in);
String input = sc.next();
sc.close();
if (isPalindromePossible(input)) {
HashMap<Character, Integer> char_map = new HashMap<>();
for (int i=0; i < input.length(); i++) {
char c = input.charAt(i);
if (!char_map.containsKey(c)) {
char_map.put(c, 1);
} else {
unique_chars += input.substring(i, i + 1);
char_map.remove(c);
}
}
generatePermutations(0, new ArrayList<StringBuilder>());
for (Character c : char_map.keySet()) {
unique_chars = c.toString();
}
if (char_map.size() > 0) {
for (String key : unique_permutations.keySet()) {
System.out.println(key + unique_chars + new StringBuilder(key).reverse().toString());
}
} else {
for (String key : unique_permutations.keySet()) {
System.out.println(key + new StringBuilder(key).reverse().toString());
}
}
} else {
System.out.println("No palindromic permutations possible");
}
}
private static void generatePermutations(int index, ArrayList<StringBuilder> results) {
if (index == 0) {
if (unique_chars.length() > 1) {
results.add(new StringBuilder(unique_chars.substring(0, 1)));
generatePermutations(index + 1, results);
} else {
unique_permutations.put(unique_chars.substring(0, 1), 1);
return;
}
} else {
ArrayList<StringBuilder> new_results = new ArrayList<>();
for (StringBuilder result : results) {
for (int i=0; i <= result.length(); i++) {
StringBuilder temp_result = new StringBuilder(result);
new_results.add(temp_result.insert(i, unique_chars.charAt(index)));
}
}
if (index == unique_chars.length() - 1) {
for (StringBuilder result : new_results) {
String str_result = result.toString();
if (!unique_permutations.containsKey(str_result)) {
unique_permutations.put(str_result, 1);
}
}
return;
}
generatePermutations(index + 1, new_results);
}
}
private static boolean isPalindromePossible(String input) {
int [] map = new int[122];
boolean even = (0 == input.length() % 2);
for (int i=0; i < input.length(); i++) {
map[input.charAt(i)]++;
}
for (int i=0; i < input.length(); i++) {
char c = input.charAt(i);
if (map[c] > 0) {
if (even && map[c] % 2 != 0) {
return false;
} else if (!even && map[c] % 2 != 0) {
even = true;
}
}
}
return true;
}
}
public List<String> palindromicPermutations(String s) {
if (TextUtils.isEmpty(s)) return null;
HashMap<String, Integer> hm = new HashMap<>();
int numOdds = 0;
for (int i = 0; i < s.length; i++) {
if (hm.containsKey(s.charAt(i))
hm.put(s.charAt(i), hm.get(s.charAt(i) + 1));
else hm.put(s.charAt(i), 1);
}
StringBuilder sb = new StringBuilder();
String single = null;
// Permutable if all chars are even (1 odd is ok)
for (Entry e: hm.entrySet()) {
int value = e.value;
if (value % 2) {
numOdds++;
single = e.key;
}
if (numOdds > 1) return null;
// Build the half key set
for (int j = 0; j <= value/2; j++) sb.append(e.key);
}
return buildPermutations(sb.toString(), single);
}
private List<String> buildPermutations(String half, String single) {
List<String> perms = new ArrayList<String>();
permutations("", half, perms);
for (String s: perms) {
s = s + single + s.reverse();
}
return perms;
}
private void permutations(String prefix, String half, List<String> op) {
int n = half.length();
if (n == 0) op.add(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), perms);
}
}
- NoOne October 06, 2016//ZoomBA : gitlab.com/non.est.sacra/zoomba/wikis/09-samples#permutation-of-a-list-containing-repeated-items l = string.toCharArray() r = [0:#|l|] permutations = set() join( @ARGS = list(r) as { l } ) where { continue ( #|set($.o)| != #|l| ) // mismatch and ignore v = str($.o,'') as { l[$.o] } continue ( v @ permutations ) // if it already occurred continue ( exists( [0 : #|v|/2 ] ) :: { v[$.o] != v[-1 - $.o] } ) permutations += v // add them there false // do not add }