Google Interview Question
Backend DevelopersCountry: United States
// Logic: if the highest frequency character count is lesser or equal
// to the sum of all other frequencies + 1, it is possible to find a
// permutation in which no two repeated characters exist
static String stringIntercalation(String str) {
if (str == null || str.length() <= 1) {
return str;
}
// Frequency count
HashMap<Character, Integer> freq = new HashMap<>();
int maxFreq = 0;
for (int i = 0; i < str.length(); i++) {
Character c = str.charAt(i);
if (!freq.containsKey(str.charAt(i))) {
freq.put(c, 1);
if (maxFreq == 0) {
maxFreq = 1;
}
} else {
freq.put(c, freq.get(c) + 1);
if (maxFreq < freq.get(c)) {
maxFreq = freq.get(c);
}
}
}
// Check if such an array exists
Integer total = 0;
Character maxFreqChar = '\0';
for (Character c : freq.keySet()) {
if (maxFreq == freq.get(c)) {
maxFreqChar = c;
}
total += freq.get(c);
}
total = total - maxFreq;
if (maxFreq > total + 1) {
return "";
}
// Get one possibility for this array
StringBuilder sb = new StringBuilder();
freq.remove(maxFreqChar);
while (!freq.isEmpty()) {
// Iterator required to modify Collection while iterating through it
Iterator<Character> iter = freq.keySet().iterator();
while (iter.hasNext()) {
Character c = iter.next();
sb.append(c);
if (maxFreq > 0) {
sb.append(maxFreqChar);
maxFreq--;
}
if (freq.get(c) > 1) {
freq.put(c, freq.get(c) - 1);
} else {
iter.remove();
}
}
}
if (maxFreq > 0) {
sb.insert(0, maxFreqChar);
}
return sb.toString();
}
// C++ program to rearrange characters in a string
// so that no two adjacent characters are same.
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
const int MAX_CHAR = 26;
struct Key
{
int freq; // store frequency of character
char ch;
// function for priority_queue to store Key
// according to freq
bool operator<(const Key &k) const
{
return freq < k.freq;
}
public:
friend ostream &operator<<(ostream& out, Key n);
};
ostream &operator<<(ostream& out, Key n)
{
return out<<"("<<n.ch<<", "<<n.freq<<")";
}
void show( priority_queue<Key> pq)
{
cout<<"{ ";
while (!pq.empty())
{
cout << pq.top();
pq.pop();
}
cout<<"}"<<endl;
}
// Function to rearrange character of a string
// so that no char repeat twice
void rearrangeString(string str)
{
int n = str.length();
// Store frequencies of all characters in string
int count[MAX_CHAR] = {0};
for (int i = 0 ; i < n ; i++)
count[str[i]-'a']++;
// Insert all characters with their frequencies
// into a priority_queue
priority_queue< Key > pq;
for (char c = 'a' ; c <= 'z' ; c++)
if (count[c-'a'])
pq.push( Key { count[c-'a'], c} );
// 'str' that will store resultant value
str = "" ;
// work as the previous visited element
// initial previous element be. ( '#' and
// it's frequency '-1' )
Key prev {-1, '#'} ;
// traverse queue
while (!pq.empty())
{
// pop top element from queue and add it
// to string.
show(pq);
Key k = pq.top();
pq.pop();
str = str + k.ch;
cout<<str<<endl;
// IF frequency of previous character is less
// than zero that means it is useless, we
// need not to push it
if (prev.freq > 0)
pq.push(prev);
// make current character as the previous 'char'
// decrease frequency by 'one'
(k.freq)--;
prev = k;
}
// If length of the resultant string and original
// string is not same then string is not valid
if (n != str.length())
cout << " Not valid String " << endl;
else // valid string
cout << str << endl;
}
// Driver program to test above function
int main()
{
string str = "bbbaacc" ;
rearrangeString(str);
return 0;
}
My Algo is
boolean find(String s){
Map<String, Integer> map = new HashMap<String, Integer>();
int maxRepeat = 0, noofChar = 0;
for(char c: s.toCharArray()){
if(map.containsKey(c)){
int i = map.getVal(c);
map.put(c, ++i);
} else {
map.put(c, 1);
}
}
for(Map.EntrySet<String, Integer> entry: map.entrySet()){
if(maxRepeat < entry.getValue()) maxRepeat = entry.getValue();
noofChar++;
}
return ((noofChar / maxRepeat) > 1) ? true : false);
}
// Graph coloring problem variation so it's NP-Complete.
// There's no polynomial complexity algorithm for it.
static String possibleIntercalation(String str) {
if (str == null || str.length() <= 1) {
return str;
}
// Convert String to ArrayList of Chars
ArrayList<Character> charList = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
charList.add(str.charAt(i));
}
// Will hold all different results of the problem
HashSet<ArrayList<Character>> resultsList = new HashSet<>();
// Used as an auxiliary memory element between recursive calls
ArrayList<Character> memory = new ArrayList<>();
if (generateAllAnagrams(charList, memory, resultsList)) {
System.out.println(memory.toString());
}
return "";
}
private static boolean generateAllAnagrams(ArrayList<Character> charList,
ArrayList<Character> memory,
HashSet<ArrayList<Character>> resultsList) {
if (charList.size() == 0) {
resultsList.add(new ArrayList<Character>(memory));
return !hasSameConsecutiveCharacters(memory);
}
for (int i = 0; i < charList.size(); i++) {
Character c = charList.remove(i);
memory.add(c);
if (generateAllAnagrams(charList, memory, resultsList)) {
return true;
}
memory.remove(memory.size() - 1);
charList.add(i, c);
}
return false;
}
private static boolean hasSameConsecutiveCharacters(ArrayList<Character> list) {
if (list == null || list.size() == 1) {
return false;
}
boolean sameConsecutive = false;
Character prev = '\0';
for (Character c : list) {
if (c == prev) {
sameConsecutive = true;
break;
} else {
prev = c;
}
}
return sameConsecutive;
}
static boolean done = false;
private static void permute(String rest, String sofar) {
if (rest.length() == 0) {
done = true;
System.out.println(sofar);
return;
}
for (int i=0; i<rest.length(); ++i) {
if (!done) {
if (sofar.length() == 0 || sofar.charAt(sofar.length()-1) != rest.charAt(i)) {
permute(rest.substring(0,i)+rest.substring(i+1),sofar+rest.charAt(i));
}
}
}
}
public static void main(String args[]) {
permute("google", "");
done = false;
permute("aoooaa","");
done = false;
permute("aoooaaa","");
done = false;
permute("aoooa","");
}
This code will check if such a string can be formed, if no then it will return null, otherwise it will return a possible string.
- Aim_Google January 12, 2018