Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
8
of 8 vote

def get_longest_palindrome(my_string) :

    #store the number of times each character occurs in the input my_string
    counter = dict.fromkeys(list(my_string), 0)
    for l in list(my_string) :
        counter[l] = counter[l] + 1

    #we will construct the largest palindrome as half_word + center + reversed(half_word)
    half_word = ''
    center = ''

    for letter in counter :
        #store in a list the number of times letter occurs divided by two and if it occurs odd or even times
        quot_mod = divmod(counter[letter],2)
        #create a string repeating letter the number of times it occurs in input my_string divided by 2
        to_add = letter * quot_mod[0]
        #add the string constructed above to the half_word
        half_word = half_word + to_add

        #if letter occurs an odd number of times use it as a center letter
        if quot_mod[1] == 1:
            center = letter
    return half_word + center + half_word[::-1]


#examples
print(get_longest_palindrome('abbacch'))
print(get_longest_palindrome('aabbsddfgh'))
print(get_longest_palindrome('akjhadajsoadjaoiwjewaodjaosid'))

- Luke Rhinehart July 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 vote

we can do it simply greedily: get the letter counter, and for even number of occurrence, keep them, odd number of occurrence, keep the largest one and take the others by dropping one letter.

- diodeBucks July 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class Solution {
    
    public static void main(String [] args) {
        
        System.out.println(getPalindrome("aha"));
        System.out.println(getPalindrome("ttaatta"));
        System.out.println(getPalindrome("abc"));
        System.out.println(getPalindrome("gggaaa"));
    }
    
    public static String getPalindrome(String str) {
        
        int [] chars = new int[27];
        
        str.chars().forEach(c -> chars[c-'a']++);
        
        StringBuilder buf = new StringBuilder();
        
        for (int i = 0; i < 27; i++) {
            if (chars[i] >= 2) {
                int count = chars[i] / 2;
                chars[i] -= count*2;
                while (count > 0) {
                    buf.append((char) (i+'a'));
                    count--;
                }
            }
        }
        
        String end = buf.toString();
        
        buf.reverse();
        
        for (int i = 0; i < 27; i++) {
            if (chars[i] >= 1) {
                buf.append((char) (i+'a'));
                break;
            }
        }
        
        return buf.toString() + end;
    }
    
}

- ugurdonmez87 July 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

post pseudocode instead guys

- guy July 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Time Complexity: O(N) where N is the size of the input string.Space is O(N).

public class Solution
{
	public static String constructPalindrome(String str)
	{
		if(str==null||str.length()==0)
		{
			return str;
		}
		if(str.length()==1)
		{
			return str;
		}
		if(isPalindrome(str))
		{
			return str;
		}
		return getLongestPalindrome(str);
	}

	private static boolean isPalindrome(String str) {
		int i=0;
		int j=str.length()-1;
		while(i<j)
		{
			if(str.charAt(i)!=str.charAt(j))
			{
				return false;
			}else
			{
				i++;
				j--;
			}
		}
		return true;
	}

	private static String getLongestPalindrome(String str) {
		int[] c=new int[26];
		for(int i=0;i<str.length();i++)
		{
			c[(int)str.charAt(i)-'a']++;
		}
		
		int oddCounts=0;
		for(int i=0;i<c.length;i++)
		{
			if(c[i]%2!=0)
			{
				oddCounts++;
				
			}
		}
		int i=0;
		while(oddCounts>1 && i<c.length)
		{
			if(c[i]%2!=0)
			{
				c[i]--;
				oddCounts--;
			}
			i++;
		}
		return buildString(c,str);
	}

	private static String buildString(int[] c,String s) {
		StringBuilder sb=new StringBuilder(s);
		int oddIdx=-1;
		int a=0;
		int b=sb.length()-1;
		for(int i=0;i<c.length;i++)
		{
			if(c[i]%2!=0)
			{
				oddIdx=i;
				
			}else
			{
				while(c[i]>0)
				{
					char v=(char)(i+'a');
					sb.setCharAt(a, v);
					sb.setCharAt(b, v);
					a++;
					b--;
					c[i]-=2;
				}
			}
		}
		if(oddIdx!=-1)
		{
			while(c[oddIdx]>0)
			{
				char x=(char)(oddIdx+'a');
				sb.setCharAt(a,x );
				sb.setCharAt(b, x);
				a++;
				b--;
				c[oddIdx]-=2;
			}
		}
		return sb.toString();
	}
}

- divm01986 July 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<string, int>  buildFreq(const string &s){
    unordered_map<string, int> freq;
    for(char ch:s){
        string c(1,ch);
        if (freq.count(c)==0){
            freq[c] = 1;
        }else{
            freq[c] += 1;
        }
    }
    return freq;
}

string longestPal(const string &s){
    unordered_map<string, int> freq = buildFreq(s);
    string L, M, R, c;
    M="";
    int count;
    
    for(auto it=freq.begin(); it!=freq.end(); it++){
        c = it->first;
        count = it->second;
        
        if(count>2){
            while(count>1){
                L=L+c;    // forward string
                R=c+R;    // reverse of L
                count=count-2;
            }
        }
        // either count is 1 to begin with or the left over is now 1
        if (count==1){
            M=c;
        }
    }
    
    return L+M+R;
}

void longPalTest(){
    string s = "gggaaa";
    cout << "Input s: " << s << endl;
    cout << "Longest Palindrome: " << longestPal(s) << endl;
}

int main(){
    longPalTest();
    return 0;
}

- jimmythefung July 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift.

//: Playground - noun: a place where people can play

import UIKit

var str = "Hello, playground"

// Keys are letters, values are letter occurences.
func createLetterCountDictionary(word:String!) -> [String: Int] {
    var result = [String: Int]()
    var characters = word.characters
    while (characters.count > 0) {
        let character = String(characters.first!)
        if (result[character] == nil) {
            result[character] = 1
            
        } else {
            result[character] = result[character]! + 1
            
        }
        characters = characters.dropFirst()
        
    }
    return result
    
}

func makePalindrome(word:String) -> String! {
    // Get a dictionary of letters/occurences and an array of sorted keys by value.
    let letterCountDictionary = createLetterCountDictionary(word)
    let sortedKeys = Array(letterCountDictionary.keys).sort({letterCountDictionary[$0] < letterCountDictionary[$1]})
    
    var leftString:String! = ""
    var centerString:String! = ""
    var rightString:String! = ""
    var centerFound = false
    
    for letter in sortedKeys {
        if var letterCount = letterCountDictionary[letter] {
            if (letterCount % 2 == 1 && centerFound == false) {
                // We have the largest odd value. Place it in the middle.
                while (letterCount > 0) {
                    centerString = centerString.stringByAppendingString(letter)
                    letterCount -= 1
                    
                }
                centerFound = true
                
            } else {
                if (letterCount % 2 == 1) {
                    // Not the largest odd value, make it even.
                    letterCount -= 1
                    
                }
                
                // We have an even amount. Split it amongst left and right.
                letterCount = letterCount / 2
                var stringToAdd:String! = ""
                while (letterCount > 0) {
                    stringToAdd = stringToAdd.stringByAppendingString(letter)
                    letterCount -= 1
                    
                }
                leftString = stringToAdd + leftString
                rightString = rightString + stringToAdd
                
            }
            
        }
        
    }
    return leftString + centerString + rightString
    
}

makePalindrome("aha") // "aha"
makePalindrome("ttaatta") // "ttaaatt"
makePalindrome("abc") // "b"
makePalindrome("gggaaa") // "gaaag"

- helloru July 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift

//: Playground - noun: a place where people can play

import UIKit

var str = "Hello, playground"

// Keys are letters, values are letter occurences.
func createLetterCountDictionary(word:String!) -> [String: Int] {
    var result = [String: Int]()
    var characters = word.characters
    while (characters.count > 0) {
        let character = String(characters.first!)
        if (result[character] == nil) {
            result[character] = 1
            
        } else {
            result[character] = result[character]! + 1
            
        }
        characters = characters.dropFirst()
        
    }
    return result
    
}

func makePalindrome(word:String) -> String! {
    // Get a dictionary of letters/occurences and an array of sorted keys by value.
    let letterCountDictionary = createLetterCountDictionary(word)
    let sortedKeys = Array(letterCountDictionary.keys).sort({letterCountDictionary[$0] < letterCountDictionary[$1]})
    
    var leftString:String! = ""
    var centerString:String! = ""
    var rightString:String! = ""
    var centerFound = false
    
    for letter in sortedKeys {
        if var letterCount = letterCountDictionary[letter] {
            if (letterCount % 2 == 1 && centerFound == false) {
                // We have the largest odd value. Place it in the middle.
                while (letterCount > 0) {
                    centerString = centerString.stringByAppendingString(letter)
                    letterCount -= 1
                    
                }
                centerFound = true
                
            } else {
                if (letterCount % 2 == 1) {
                    // Not the largest odd value, make it even.
                    letterCount -= 1
                    
                }
                
                // We have an even amount. Split it amongst left and right.
                letterCount = letterCount / 2
                var stringToAdd:String! = ""
                while (letterCount > 0) {
                    stringToAdd = stringToAdd.stringByAppendingString(letter)
                    letterCount -= 1
                    
                }
                leftString = stringToAdd + leftString
                rightString = rightString + stringToAdd
                
            }
            
        }
        
    }
    return leftString + centerString + rightString
    
}

makePalindrome("aha") // "aha"
makePalindrome("ttaatta") // "ttaaatt"
makePalindrome("abc") // "b"
makePalindrome("gggaaa") // "gaaag"

- Anonymous July 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Short and simple:

def maxPalindrome(string):
    count = collections.Counter(string)
    odds = {key: val for (key, val) in count.items() if val % 2 != 0}
    evens = {key: val for (key, val) in count.items() if val % 2 == 0}
    maxodds = "" if not odds else max(odds)
    result = ""
    for char in evens:
        result += char * (count[char] // 2)
    for char in odds:
        if char != maxodds:
            result += char * ((count[char] - 1) // 2)
    return result + (maxodds * odds.get(maxodds, 0)) + result[::-1]

- agave July 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function LongestPalindrome(str)
{
  var oHash = new Object();
		
  for(var i=0; i<str.length; i++)
    oHash[str[i]] = typeof(oHash[str[i]]) == "undefined" ? 1 : oHash[str[i]]+1; 
		
  var cCenter;
		
  // Option I.
  var sLP = "";
  
  for(var char in oHash)
  {
    if(oHash[char] % 2 == 1 && !cCenter)
      cCenter = char;
    if(oHash[char] > 1)
      sLP += Array((oHash[char] >> 1) + 1).join(char);
  }
  
  if(cCenter)
    sLP += cCenter;
		
  for(var i=sLP.length-2; i>=0; i--)
    sLP += sLP[i];
		
  return sLP;
		
  /*
  // Option II.
  var oLP = new Array();
  
  for(var char in oHash)
  {
    if(oHash[char] % 2 == 1 && !cCenter)
      cCenter = char;
    if(oHash[char] > 1)
    {
      for(var j=0; j<(oHash[char] >> 1); j++)
      {
        oLP.push(char);
        oLP.unshift(char);
      }
    } // if
  } // for

  if(cCenter)
    oLP.splice(oLP.length ? oLP.length >> 1 : 0, 0, cCenter)
		
  return oLP.join("");
  */
		
} // LongestPalindrome

- Harel Gruia July 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

template <typename Container>
Container Reversed(Container c) {
  std::reverse(c.begin(), c.end());
  return c;
}

template <typename Container>
Container FilledWith(const typename Container::value_type& item, int n) {
  Container c(n, item);
  return c;
}

std::string LongestPalindrome(const std::string& s) {
  std::unordered_map<char, int> character_occurances;
  for (char c : s) {
    ++character_occurances[c];
  }

  std::string evens;
  std::string max_odds;

  for (auto character_frequency : character_occurances) {
    std::size_t tossed = 0;
    while (character_frequency.second % 2 == 1) {
      ++tossed;
      --character_frequency.second;
    }

    evens += FilledWith<std::string>(character_frequency.first,
                                     character_frequency.second / 2);
    if (tossed > max_odds.size()) {
      max_odds = FilledWith<std::string>(character_frequency.first, tossed);
    }
  }

  return evens + max_odds + Reversed(evens);
}

int main() {
  std::cout << LongestPalindrome("aha") << std::endl;
  std::cout << LongestPalindrome("ttaatta") << std::endl;
  std::cout << LongestPalindrome("gggaaa") << std::endl;
}

- The Kid July 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

template <typename Container>
Container Reversed(Container c) {
  std::reverse(c.begin(), c.end());
  return c;
}

template <typename Container>
Container FilledWith(const typename Container::value_type& item, int n) {
  Container c(n, item);
  return c;
}

std::string LongestPalindrome(const std::string& s) {
  std::unordered_map<char, int> character_occurances;
  for (char c : s) {
    ++character_occurances[c];
  }

  std::string evens;
  std::string max_odds;

  for (auto character_frequency : character_occurances) {
    std::size_t tossed = 0;
    while (character_frequency.second % 2 == 1) {
      ++tossed;
      --character_frequency.second;
    }

    evens += FilledWith<std::string>(character_frequency.first,
                                     character_frequency.second / 2);
    if (tossed > max_odds.size()) {
      max_odds = FilledWith<std::string>(character_frequency.first, tossed);
    }
  }

  return evens + max_odds + Reversed(evens);
}

int main() {
  std::cout << LongestPalindrome("aha") << std::endl;
  std::cout << LongestPalindrome("ttaatta") << std::endl;
  std::cout << LongestPalindrome("gggaaa") << std::endl;
}

- The Kid July 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity is O(n):

std::string FindLongestPalindrome(const std::string &str) {
    // 1. build charCountMap with str
    typedef std::unordered_map < char, int > CharCountMap;
    CharCountMap charCountMap;
    for (int i = 0; i < str.size(); ++i) {
        char c = str[i];
        CharCountMap::iterator it = charCountMap.find(c);
        if (it == charCountMap.end()) {
            charCountMap.insert(CharCountMap::value_type(c, 1));
        } else {
            it->second++;
        }
    }

    // 2. build left half part of palindrome and find if there is a middleChar
    // 0 means no middleChar
    char middleChar = 0;
    std::string result;
    for (CharCountMap::iterator i = charCountMap.begin(); i != charCountMap.end(); ++i) {
        char c = i->first;
        int count = i->second;
        if (count >= 2) {
            for (int j = 0; j < count / 2; ++j) {
                result += c;
            }
        }
        if (middleChar == 0 && count % 2 == 1) {
            middleChar = c;
        }
    }

    // 3. append middleChar if needed
    int size = result.size();
    if (middleChar != 0) {
        result += middleChar;
    }

    // 4. append right half part with left half part
    for (int i = size - 1; i >= 0; --i) {
        result += result[i];
    }

    return result;
}

- SW July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {

	public static void main(String[] args) {
		//String s = "ttaatta"; //attatta
		//String s = "ttaatt"; //atttta
		String s = "ttaata"; //attta
		printLongestPalindrome(s);
	}
	
	public static void printLongestPalindrome(String s){
		HashMap<Character,Integer> map = new HashMap<>();
		for(Character c:s.toCharArray()){
			if(map.containsKey(c)){
				map.put(c, map.get(c)+1);
			}else{
				map.put(c, 1);
			}
		}
		
		int oddMaxCount = 0;
		StringBuffer result1 = new StringBuffer("");
		StringBuffer result2 = new StringBuffer("");
		for(Character key:map.keySet()){
			if(map.get(key)%2!=0){
				oddMaxCount = Math.max(oddMaxCount, map.get(key));
			}
			for(int i=0;i<map.get(key)/2;i++){
				result1.append(key);
			}
		}
		char middle='q';
		boolean middleExists = false;
		for(Character key:map.keySet()){
			if(map.get(key)%2!=0 && map.get(key)==oddMaxCount){
				middle = key;
				middleExists = true;
			}
			for(int i=0;i<map.get(key)/2;i++){
				result2.append(key);
			}
		}
		
		if(middleExists)System.out.println(result1+Character.toString(middle)+result2.reverse());
		else System.out.println(result1+""+result2.reverse());
	}
}

- settyblue July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_polindrom(s):
    d = collections.defaultdict(int)
    for char in s:
        d[char] += 1
    result = []
    odd_added = False
    for k, v in d.items():
        if not odd_added:
            if v % 2 != 0:
                odd_added = True
                result = result[:(len(result)/2)] + [k] * v + result[(len(result)/2):]
        else:
            result += [k] * (v // 2)
            result = [k] * (v // 2) + result
    return "".join(result)

- tkachoff July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var LP = LP || {};

LP.find = function(str) {
var arr = str.split("");
var l = arr.length;

if (l === 0) {
return false;
}

if (l === 1) {
return arr;
}

var dict = [];
var u = [];

for (var i = 0; i < l; i++) {
if (!dict[arr[i]]) {
dict[arr[i]] = 1;
u.push(arr[i]);
} else {
dict[arr[i]] = dict[arr[i]] + 1;
}
}

var s = "";
var singles = [];
var tmp = [];
while (u.length) {
var val = u.pop()
var max = dict[val];
if (max === 1) {
singles.push(val);
} else {
while (max % 2 !== 0) {
max--;
}
for (var k = 0; k < max; k = k + 2) {
tmp.unshift(val);
tmp.push(val);
}
}
}
s = tmp.join("");
if (singles.length > 0) {
var a = s.split("");

var a1 = a.slice(0, Math.floor(a.length / 2));
var a2 = a.slice(Math.floor(a.length / 2));

a1.push(singles[0]);
return a1.concat(a2).join("");
} else {
return s;
}
};

LP.find("abbacch");

- jscoder August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var LP = LP || {};

LP.find = function(str) {
    var arr = str.split("");
    var l = arr.length;

    if (l === 0) {
        return false;
    }

    if (l === 1) {
        return arr;
    }

    var dict = [];
    var u = [];

    for (var i = 0; i < l; i++) {
        if (!dict[arr[i]]) {
            dict[arr[i]] = 1;
            u.push(arr[i]);
        } else {
            dict[arr[i]] = dict[arr[i]] + 1;
        }
    }

    var s = "";
    var singles = [];
    var tmp = [];
    while (u.length) {
        var val = u.pop()
        var max = dict[val];
        if (max === 1) {
            singles.push(val);
        } else {
            while (max % 2 !== 0) {
                max--;
            }
            for (var k = 0; k < max; k = k + 2) {
                tmp.unshift(val);
                tmp.push(val);
            }
        }
    }
    s = tmp.join("");
    if (singles.length > 0) {
        var a = s.split("");

        var a1 = a.slice(0, Math.floor(a.length / 2));
        var a2 = a.slice(Math.floor(a.length / 2));

        a1.push(singles[0]);
        return a1.concat(a2).join("");
    } else {
        return s;
    }
};

LP.find("abbacch");

- jscoder August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from collections import defaultdict
def findLongestPalin(string):
	char_dict = defaultdict(int)
	for char in string:
		char_dict[char] += 1
	begin = ""
	end = ""
	mid = ""
	for char in char_dict:
		if char_dict[char] % 2 == 0:
			begin += char * int(char_dict[char] / 2)
			end += char * int(char_dict[char] / 2)
		else:
			 begin += char * int(char_dict[char] / 2)
			 end += char * int(char_dict[char] / 2)
			 mid += char 
	if len(mid) > 0: 
		palin = begin + mid[0] + end[::-1]
	else:
		palin = begin + end[::-1]
	return palin

- potatoML August 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
1. Count character occurence in input per character with a hash table
2. Construct palindrome by taking two characters out and placing them at the start and end
3. If at least one character has odd occurence, place one of it in the middle
*/

#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

string ConstructPalindrome(const string& input)
{
	int size = 0; // size of the resulting palindrome
	unordered_map<char, int> cm; // character count map

	// count each character, if a character occures an even amount of time, 
	// increase the palindrome size by that size (2 each time)
	for (char c : input)
	{
		unordered_map<char, int>::iterator it;
		if ((it = cm.find(c)) != cm.end())
		{
			it->second++;
			if (it->second % 2 == 0) size += 2;
		}
		else
		{
			cm[c] = static_cast<int>(1);
		}
	}

	// fix size for the case there is at least one character with an odd count
	// and reserve space for result
	if (size < input.size()) size++; 
	string result(size, ' ');

	// construct result
	int i = 0;
	int j = size - 1;
	for (auto p : cm)
	{
		while (p.second > 1) 
		{
			result[i++] = p.first;
			result[j--] = p.first;
			p.second -= 2;
		}
		if (p.second == 1) result[size / 2] = p.first;
	}
	return result;
}



int main()
{
	cout << "aha: '" << ConstructPalindrome("aha") << "'" << endl;
	cout << "ttaatta: '" << ConstructPalindrome("ttaatta") << "'" << endl;
	cout << "abc: '" << ConstructPalindrome("abc") << "'" << endl;
	cout << "gggaaa: '" << ConstructPalindrome("gggaaa") << "'" << endl;

	getchar();
}

- Chris August 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def longestPalindrome(s):
    ss, dd = set(), []
    for c in s:
        if ss and c in ss:
            dd.append(c)
            ss.discard(c)
        else:
            ss.add(c)

    return "".join(dd) + (list(ss)[0] if ss else "") + "".join(dd[::-1])

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

def longestPalindrome(s):
    ss, dd = set(), []
    for c in s:
        if ss and c in ss:
            dd.append(c)
            ss.discard(c)
        else:
            ss.add(c)

    return "".join(dd) + (list(ss)[0] if ss else "") + "".join(dd[::-1])

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

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 */
public class LongestPalindrome {

    static String longestPalin(String s) {
        Map<Character, Integer> charCount = new HashMap<Character, Integer>();
        for (char c : s.toCharArray()) {
            if (charCount.containsKey(c)) {
                charCount.put(c, charCount.get(c) + 1);
            } else {
                charCount.put(c, 1);
            }
        }
        Set<Map.Entry<Character, Integer>> entries = charCount.entrySet();
        Map.Entry<Character, Integer> maxOddEntry = getMaxOddEntry(entries);
        Stack<Map.Entry<Character, Integer>> stack = new Stack<Map.Entry<Character, Integer>>();
        StringBuilder result = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : entries) {
            Integer value = entry.getValue();
            Character character = entry.getKey();
            if (maxOddEntry != null && character == maxOddEntry.getKey()) {
                continue;
            }
            append(result, character, value / 2);
            stack.push(entry);
        }
        if (maxOddEntry != null) {
            append(result, maxOddEntry.getKey(), maxOddEntry.getValue());
        }
        while (!stack.isEmpty()) {
            Map.Entry<Character, Integer> entry = stack.pop();
            append(result, entry.getKey(), entry.getValue() / 2);
        }
        return result.toString();
    }

    private static void append(StringBuilder result, Character key, int n) {
        for (int i = 0; i < n; i ++) {
            result.append(key);
        }
    }

    private static Map.Entry<Character, Integer> getMaxOddEntry(Set<Map.Entry<Character, Integer>> entries) {
        int maxOddCount = 0;
        Map.Entry<Character, Integer> result = null;
        for (Map.Entry<Character, Integer> entry : entries) {
            Integer value = entry.getValue();
            if (value % 2 == 1 && value > maxOddCount) {
                maxOddCount = value;
                result = entry;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(longestPalin("aha"));
        System.out.println(longestPalin("ttaatta"));
        System.out.println(longestPalin("abc"));
        System.out.println(longestPalin("gggaaa"));
    }
}

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

given = 'ttaatta'
out = ""
single = ''

curChar = None
for x in sorted(given):
  if curChar is None:
    curChar = x
  elif x == curChar:
    out += x
    curChar = None
  else:
    single = curChar
    curChar = x

if curChar is not None:
  single = curChar

print out + single + out[::-1]

- sleepy October 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// ZoomBA
def max_palindrome( string ){
  // create a mapping of char -> count
  cb = mset ( string.value )
  #(m,M) = minmax( cb ) :: {
    #(l,r) = $.item ; (2 /? l.value) || (l.value < r.value) }
  middle = (2 /? M.value) ? '' : str( M.key )
  // generate palindrome by appending v to left and right
  fold ( cb , middle ) -> {
    // no need to take care of even n odd because, (2x+1)/2 -> x anyways
    v = str( $.item.key ) ** ($.item.value /2 )
    v + $.partial + v
  }
}
s = 'akjhadajsoadjaoiwjewaodjaosid'
println ( max_palindrome( s ) )

- NoOne October 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A working solution in Python using recursion.

def longest_palindrome(string):
    # count how many times each char shows up
    count = {}
    for char in string:
        if char in count:
            count[char] += 1
        else:
            count[char] = 1
    # if there are multiple odds, leave only one odd
    odd_appeared = False
    odd_char = ""
    for key in count:
        if count[key] % 2 == 1:
            if odd_appeared:
                count[key] -= 1
            else:
                odd_appeared = True
                odd_char = key
    # go through the dictionary and reconstruct the palindrome string
    palindrome = ""
    for key in count:
        chars = count[key]/2 * key
        palindrome = palindrome + chars
        palindrome = chars + palindrome
    if odd_appeared:
        n = len(palindrome)
        palindrome = palindrome[:n/2] + odd_char + palindrome[n/2:]
    return palindrome

print longest_palindrome('ttaatta')
print longest_palindrome('abc')
print longest_palindrome('aha')
print longest_palindrome('a')
print longest_palindrome('')

- kojino November 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from collections import Counter
def longest_palin(string):
    cntr = Counter(string)    
    
    odd = False
    palin = ""
    for letter, cnt in cntr.items():
        palin = letter*(cnt/2) + palin + letter*(cnt/2)
        if not odd and cnt%2:
            mid = len(palin)/2
            palin = palin[:mid] + letter + palin[mid:]
            odd = True
    return palin
                        
print longest_palin("ttaatbcgdjakkjgdtaat")

- Nitish Garg January 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
#include<list>
#include<unordered_map>

using namespace std;

list<char> generate_maximum_palindrom(const string& str){
    list<char> palindrom {};
    unordered_map<char, int> counter {};
    int largest_odd = -1;
    char largest_odd_char = ' ';
    
    for(char c:str){
        counter[c] ++;
        
        if(counter[c] % 2 != 0 && counter[c] > largest_odd){
            largest_odd_char = c;
            largest_odd = counter[c];
        }
    }
    
    if(largest_odd > -1){
        while(counter[largest_odd_char]--){
            palindrom.push_back(largest_odd_char);
        }
    }
        
    for(auto it = counter.begin(); it != counter.end(); it++){
        while(it->second >= 2){
            palindrom.push_back(it->first);
            palindrom.push_front(it->first);
                
            it->second -= 2;
        }
    }
    
    
    return palindrom;
}

int main(){
    string str = "akjhadajsoadjaoiwjewaodjaosid";
    
    for(char c : generate_maximum_palindrom(str))
        cout << c;
    cout << endl;
}

- hamid.moghadam85 September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Really a google question ?

Plain O(n).

Collect all char in a hash.
For each char in hash
if(hash.containsKey(char) > 1){
put that char in new string, i & strlen(str) - i position
update hash.add(char , (hash.containsKey(char) - 2))
} else {
int val = hash.get(char);
hash.add(char, hash.containsKey(char) - 1);
if(!hash.isempty()){
Error:-> Cannot be formed
}
}

- hprem991 July 22, 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