Google Interview Question Software Engineers
Country: India
Interview Type: Phone Interview
This logic is correct except for the FancyShuffle should return bool, and specifically false if the string can't be formed. Here is modified code :
static bool FancyShuffle(ref string s)
{
bool result = true;
List<KeyValuePair<char, int>> charFreqList = GetCharFreq(s);
StringBuilder[] rows = new StringBuilder[charFreqList[0].Value];
int r = 0;
for (int i = 0; i < charFreqList.Count(); i++)
{
char c = charFreqList[i].Key;
for (int j = 0; j < charFreqList[i].Value; j++)
{
if (rows[r] == null) rows[r] = new StringBuilder();
rows[r].Append(c);
r = (r + 1) % rows.Length;
}
}
StringBuilder sb = new StringBuilder();
foreach (StringBuilder row in rows)
{
if(sb.ToString() != String.Empty)
{
if(sb[sb.Length-1] == row[0])
return false;
}
sb.Append(row);
}
return result;
}
static List<KeyValuePair<char, int>> GetCharFreq(string s)
{
Dictionary<char, int> charFreq = new Dictionary<char, int>();
foreach (char c in s)
{
int cFreq = 0;
if (charFreq.TryGetValue(c, out cFreq))
{
charFreq.Add(c, cFreq + 1);
}
else
{
charFreq.Add(c, 1);
}
}
List<KeyValuePair<char, int>> charFreqList = charFreq.ToList();
charFreqList.Sort((c1, c2) => { return c1.Value.CompareTo(c2.Value); });
return charFreqList;
}
Do we really need to sort all the characters,i.,e need to find second most frequent char and so on ?? I guess only finding the max one (char) will be enough.
This is the nicest solution, good work!
It seems that all the solutions here require "pre-processing" all characters by their count. It would be nice to see an algorithm that does minimal work, i.e. if a string does not have a character that is repeated consecutively, then it only requires a single pass through the string (which does nothing). Whereas a string like 'hello' would only require a single swap. Not sure how manageable this would be.
No need for sorting by the character frequency. All that matters is the largest group because the array is not cyclic. This means AAAABBB would be properly solved to ABABABA whereas if we started populating B characters we would have BABABAA which is wrong.
O(n) solution possible, we have only to find the max freq instead of sorting:
#include <iostream>
#include <unordered_map>
bool fancyShuffle(char* s)
{
auto charCount = std::unordered_map<char, int>();
int i;
// build hash map of character count
for (i = 0; s[i] != '\0'; i++)
{
auto currentCountIt = charCount.find(s[i]);
if (currentCountIt == std::end(charCount))
{
charCount.insert(std::make_pair(s[i], 1));
}
else
{
currentCountIt->second++;
}
}
int len = i;
if (len <= 1)
{
return true;
}
// Find the largest group
auto maxPairIt = std::begin(charCount);
for (auto it = std::begin(charCount); it != std::end(charCount); ++it)
{
if (it->second > maxPairIt->second)
{
maxPairIt = it;
}
}
// Check if shuffling is possible
if (maxPairIt->second > (len+1)/2)
{
return false;
}
auto current = maxPairIt;
i = 0;
do
{
// Start populating on alternating positions
for (int j = 0; j < current->second; j++)
{
s[i] = current->first;
i += 2;
if (i >= len)
{
i = 1;
}
}
charCount.erase(current);
current = std::begin(charCount);
} while (current != std::end(charCount));
return true;
}
int main()
{
//char s[] = "hhhhhhhjsjsjksuwwuueueiiao";
//char s[] = "xxxxxyyyy";
//char s[] = "xxxxyyyyy";
//char s[] = "xxxxxyyyyy";
char s[] = "xxxxyyyy";
if (fancyShuffle(s))
{
std::cout << s;
}
return 0;
}
I think this is clever to on O(n) order of growth. At the beginning I though I wouldn't work but it does work.
java implementation:
public static boolean fancy_shuffle(String s) {
HashMap<Character, Integer> hm = new HashMap<>();
int max = 0;
char maxChar = 0;
for (char i : s.toCharArray()) {
if (hm.containsKey(i)) {
hm.put(i, hm.get(i) + 1);
} else {
hm.put(i, 1);
}
if (hm.get(i) > max) {
max = hm.get(i) + 1;
maxChar = i;
}
}
if (max > (s.length()+1)/2.0) {
return false;
}
Set<Character> hs = hm.keySet();
hs.remove(maxChar);
Iterator<Character> iterator = hs.iterator();
char[] sCopy = s.toCharArray();
int tracker = 0;
while (tracker < sCopy.length) {
for (char i : hs) {
if (hm.get(i) > 0) {
if (max > 0) {
sCopy[tracker++] = maxChar;
max--;
}
sCopy[tracker++] = i;
hm.put(i, hm.get(i) - 1);
} else {
hs.remove(i);
}
}
}
s = String.copyValueOf(sCopy);
return true;
}
We should not add 1 while calculating the max. Below is the update piece of code.
if (hm.get(i) > max) {
max = hm.get(i);
maxChar = i;
}
This implementation is poor but it does seem to work.
module.exports = function (s) {
var freqMap = {};
var array = [];
var tmp = [];
var i;
var key;
var total = 0;
var most = 0;
var type = null;
for (i = 0; i < s.length; i++) {
char = s.charAt(i);
freqMap[char] = freqMap[char] || [];
freqMap[char].push(char);
}
for (key in freqMap) {
if (freqMap.hasOwnProperty(key)) {
total += freqMap[key].length;
if (freqMap[key].length > most) {
type = key;
most = freqMap[key].length;
}
array.push(freqMap[key]);
}
}
// console.log('"' + type + '"', most, total);
if ( total - most < most - 1 ) {
return false;
}
array.sort(function (a, b) {
if (a.length > b.length) {
return -1;
} else if (a.length < b.length) {
return 1;
}
return 0;
});
// console.log(array);
tmp.push(array.shift());
while (tmp.length) {
var target = tmp.pop();
var src = array.shift();
if (!src) {
array.push(target);
continue;
}
if (array.length && target.length > src.length + 1) {
tmp.push(target);
tmp.push(src);
continue;
}
var res = [];
var q = Math.max(target.length, src.length);
for (i = 0; i < q; ++i) {
target[i] && res.push(target[i]);
src[i] && res.push(src[i]);
}
tmp.push(res);
}
return array[0].join("");
};
console.log(module.exports('aaaaabbbbcccceeeeeeeeeeddddffghijkl'))
//output
'eaedecefeaebeceheaedclabckadfbjdgbi'
This can be solved using backtracking.
1. sort the string based on number of occurrences. e.g. d(3),a(2),b(2),c(1)
2. start from the most frequent char, and decrease the count to -1.
3. now do the same next most frequent char and keep updating the count.
4. if two characters collide, backtrack and repeat the same with next most frequent char.
consideration:function ascii gives us the ascii code for any given char and char function converts each ascii to a character
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
WriteTheNewString(a, m, length(s))
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
write(char(a[i]));
m:=i;
a[i]:=a[i]-1;
WriteTheNewString(a, m, l-1);
}
Brief algo
1> Sort characters by their count
2> Now pick character with higest count and then character with second highest count
3> put them in string . Decrement their count
4>repeat until no character left
5> Also initially check if a particular character's count is n/2 +1. Then not possible.
This seems like a nice solution. But couldn't this be optimized further in that we only need step 5? Why do we need the rest of the steps?
Seems that you are missing the step where you put the two picked characters back in-order to your sorted by count characters.
As if we only take the two highest and put them in a string until there no character left it not work wel.
For example AABBCC will not return false according to your algorithm
As seems like the algorithm pics AA BB to create the string creating
ABAB then you are left with "CC".
When the result should be: ABCABC.
This answer is what I am thinking, but explicitly use a max heap to store the characters by their count. BuildMaxHeap still runs in O(n) and then consecutively decrease the priority (i.e. a character's count) of the root and its max child. This way, the root will always be the character with the highest count remaining.
Brief algo
1> Sort characters by their count
2> Now pick character with higest count and then character with second highest count
3> put them in string . Decrement their count
4>repeat until no character left
5> Also initially check if a particular character's count is n/2 +1. Then not possible.
consideration:function ascii gives us the ascii code for any given char and char function converts each ascii to a character
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
WriteTheNewString(a, m, length(s))
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
write(char(a[i]));
m:=i;
a[i]:=a[i]-1;
WriteTheNewString(a, m, l-1);
}
consideration:function ascii gives us the ascii code for any given char and char function converts each ascii to a character
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
WriteTheNewString(a, m, length(s))
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
write(char(a[i]));
m:=i;
a[i]:=a[i]-1;
WriteTheNewString(a, m, l-1);
}
consideration:function ascii gives us the ascii code for any given char and char function converts each ascii to a character
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
WriteTheNewString(a, m, length(s))
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
write(char(a[i]));
m:=i;
a[i]:=a[i]-1;
WriteTheNewString(a, m, l-1);
}
Here is the latest one, adding check for the possibility,
consideration:function ascii gives us the ascii code for any given char and char function converts each ascii to a character
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
return WriteTheNewString(a, m, length(s));
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return 0;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
if pos==-1 return -1;
write(char(a[i]));
m:=i;
a[i]:=a[i]-1;
WriteTheNewString(a, m, l-1);
}
---adding the check for possibility
consideration:function ascii gives us the ascii code for any given char and char function converts each ascii to a character
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
return WriteTheNewString(a, m, length(s));
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return 0;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
if pos==-1 return -1;
write(char(a[i]));
m:=i;
a[i]:=a[i]-1;
WriteTheNewString(a, m, l-1);
}
---adding the check for possibility
consideration:function ascii gives us the ascii code for any given char and char function converts each ascii to a character
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
return WriteTheNewString(a, m, length(s));
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return 0;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
if pos==-1 return -1;
write(char(a[i]));
m:=i;
a[i]:=a[i]-1;
WriteTheNewString(a, m, l-1);
}
---adding the check for possibility
boolean fancy_shuffle(s: string)
{
var
a: array [0..255] of integer;
m: int;
ParseString(s, a); // after this we know count of each character
// a contains the count of each ascii code in string s
m := -1; // which one just printed, set to -1 as nothing is printed yet.
if length(s)>0
return WriteTheNewString(a, m, length(s));
}
ParseString(s: string, a: array of int)
{
for i=0 to 255 do
a[i]=0;
for i=1 to length(s) do
{
a[ascii(s[i])] = a[ascii(s[i])] + 1;
}
}
WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return 0;
max:=0;
pos:=-1;
for i=0 to 255 do // find the character with max remaining count
{
if a[i] > max and m<>i
{
max:=a[i];
pos:=i;
}
}
if pos==-1 return -1;
write(char(a[pos]));
m:=pos;
a[pos]:=a[pos]-1;
WriteTheNewString(a, m, l-1);
}
1. using a HashMap<Character, Integer> traverse String inserting each unique found chars and it's occurences in String. keep track of maxUniqueCount found.
2. if maxUniqueCount > (n/2) + 1 return false;O
else copy contents of Map to ArrayList and sort list by occurrence count.
3. after list is sorted start from highest count and pick one char of it and decrement counter, keep traversing list picking pairs with highest and second highest chars and place them one after another in sequence until both reach count 0.
4. If you reach count 0 for all Chars you reached the final solution String.
Complexity: O (n * log(n))
# Solution using Python 2.7
def fancyShuffle (inStr):
inDict = createDict (inStr)
tempArray = list([k,v] for k,v in inDict.items())
tempArray.sort(key = lambda tup:tup[1], reverse = True)
tempArrayLen = len(tempArray)
if (fancyShuffle_Check(tempArray) == False):
return False
totalCount = sum (v for k,v in tempArray)
inStr [:]= ['_' for x in range (totalCount)][:]
### odd cycle
i = 0
k = 0
while ((i < totalCount) and (k < tempArrayLen)):
if (tempArray[k][1] == 0):
k += 1
inStr [i] = tempArray[k][0]
tempArray[k][1] -= 1
i += 2
i = 1
while ((i < totalCount) and (k < tempArrayLen)):
if (tempArray[k][1] == 0):
k += 1
inStr [i] = tempArray[k][0]
tempArray[k][1] -= 1
i += 2
return True
def fancyShuffle_Check (tempArray):
maxCharCount = tempArray[0][1]
count = sum ( v for k,v in tempArray[1:] )
if (maxCharCount <= count+1):
return True
return False
def createDict (inStr):
inDict = {}
for char in inStr:
if (char in inDict):
inDict[char] += 1
else:
inDict[char] = 1
return inDict
inStr = list('aabbcbccc')
print (fancyShuffle (inStr), inStr)
Here is my implementation in Python:
def fancy_shuffle(list):
count_table = build_count_table(list)
lcl = make_list_of_letter_count(count_table)
from math import floor, ceil
if lcl[len(lcl) - 1][1] > ceil(len(list) / 2):
return False
else:
lcl = build_list_from_lcl(lcl)
return zipper_merge(lcl[int(floor(len(lcl)/2)):], lcl[:int(floor(len(lcl)/2))])
def zipper_merge(first, second):
res = []
while len(second) > 0:
f = first.pop()
s = second.pop()
res.extend([f, s])
if len(first) != 0:
res.extend([first.pop()])
return res
def build_list_from_lcl(lcl):
res = []
for tuple in lcl:
res.extend([tuple[0] for x in range(tuple[1])])
return res
def make_list_of_letter_count(count_table):
list = []
for letter in count_table.keys():
list.append((letter, count_table[letter]))
from operator import itemgetter
list = sorted(list, key=itemgetter(1))
return list
def build_count_table(list):
count_table = {}
for char in list:
if not char in count_table.keys():
count_table[char] = 1
else:
count_table[char] = count_table[char] + 1
return count_table
print fancy_shuffle("adjskadjladja")
Not a big an of the solution that I came up but it is not bad.
First I determine the repetition of the characters in a hashtable then I use a "Heap" which I can simulate with a SortedDictionary and take the max number ocurrence and mix with the second max occurences till the SortedDictionary is empty.
This assumes that there is a reverse comparison in order to make the SortedDictionary act like a MaxHeap.
This algorithm has an O(n + nlogn) order of growth but it does many nlogn operations when utilizing the SortedDictionary some could be removed by using a HashSet to supplement the behavior as lookups of the SortedDictionary are log(n) but decided to remove that code to simplify the code.
There also could be minor optimizations where when populating the HashSet (Dictionary) it could detect if the string already is a fancy shuffle so it does not need to do anything else.
I think there might be a better algorithm which remove lost of the nlogn operations. Maybe using a combination of a SortedDictionary and a Queue where the Queue maintains the two largest number of repeated characters and it adds more as the dequeue values reaches the same value as the max of remaining elements in the SortedDictionary.
public static fancy_shuffle(string S)
{
Dictionary<char, int> ht = new Dictionary<char, int>();
foreach(char c in S)
{
if(!ht.ContainsKey(c))
{
ht.Add(c, 1);
}
else
{
ht[c]++;
}
}
var sd = new SortedDictionary<int, List<char>>(/* need reverse comparer */);
foreach(var kvp in ht)
{
if(!hsd.Contains(kvp.Value))
{
sd.Add(kvp.Value, new List<char>(){ kvp.Key });
}
else
{
sd[kvp.Value].Add(kvp.Key);
}
}
StringBuilder sb = new StringBuilder();
Tuple<char, int> prev = null;
while(sd.Count != 0)
{
// Assuming that it has a reverse comparer to make getting the largest value
// the first in the SortedDictionary as this is an O(1) operation.
var kvp = sd.First();
int occur = kvp.Key
char c = kvp.Value.First();
sb.Append(c);
if(kvp.Value.Count == 1)
{
sd.Remove(occur);
}
else
{
kvp.Value.RemoveAt(0);
}
// Add again the previous element if needed
if(prev != null && prev.Item2 > 0)
{
if(!hsd.Contains(prev.Item2))
{
sd.Add(prev.Item2, new List<char>(){ prev.Item1});
}
else
{
sd[prev.Item2].Add(prev.Item1);
}
}
// Make the current the previous element
prev = new Tuple<char, int>(c, ocurr - 1 );
}
// This means there is an element left that requires to be duplicated
// in order to make the fancy shuffle work
if(prev != null && prev.Item2 > 0)
{
throw new ArgumentException("This string can't be fancy shuffled");
}
return sb.ToString();
}
1. Make sure that there are no characters that take more than Math.ceil(string.length/2)
2. Sort it,
3. Split in two arrays exactly in the middle
4. Iterate over both of them popping the first letter from each
Somewhat clunky but here's one solution utilizing a counting system
in python:
def fancy_shuffle(word):
output = ""
chars = {}
for i in range(0,len(word)):
if chars.get(word[i],None):
chars[word[i]] += 1
else:
chars[word[i]] = 1
val_sum = 1
while val_sum > 0:
val_sum = 0
for letter, count in chars.iteritems():
if count == 0:
continue
if output and output[len(output)-1] == letter:
return False
output += letter
chars[letter] -= 1
val_sum += count
return output
The runtime is O(n), it takes O(n) time to run through the initial word and organize all the letter occurrences with their counts in the lookup table. It then takes another O(n) time to look through the table doing consecutive iterations and decrementing the letter counts as each is placed into the shuffled string.
Space efficiency is O(n)
struct CharData
{
CharData() : character('a'), count(0) {}
char character;
int count;
};
bool fancy_shuffle(char *s)
{
if (!s)
return false;
int len = strlen(s);
std::vector<CharData> lookup(26);
int max_count = 0;
int uniq_count = 0;
for (int i = 0; i < len; ++i)
{
if (lookup[s[i] - 'a'].count == 0)
{
++uniq_count;
lookup[s[i] - 'a'].character = s[i];
}
++lookup[s[i] - 'a'].count;
if (max_count < lookup[s[i] - 'a'].count)
max_count = lookup[s[i] - 'a'].count;
}
if (max_count >= (len + 1) / 2)
return false;
std::sort(lookup.begin(), lookup.end(), [](const CharData &l, const CharData &r){return l.count > r.count;});
lookup.resize(uniq_count);
int s_idx = 0;
int lookup_idx_b = 0;
int lookup_idx_e = lookup.size() - 1;
while (s_idx < len)
{
if (!lookup[lookup_idx_b].count)
lookup_idx_b++;
if (!lookup[lookup_idx_e].count)
lookup_idx_e--;
if (lookup[lookup_idx_b].count)
{
s[s_idx++] = lookup[lookup_idx_b].character;
lookup[lookup_idx_b].count--;
}
if (lookup_idx_e > lookup_idx_b)
{
s[s_idx++] = lookup[lookup_idx_e].character;
lookup[lookup_idx_e].count--;
}
}
return true;
}
struct CharData
{
CharData() : character('a'), count(0) {}
char character;
int count;
};
bool fancy_shuffle(char *s)
{
if (!s)
return false;
int len = strlen(s);
std::vector<CharData> lookup(26);
int max_count = 0;
int uniq_count = 0;
for (int i = 0; i < len; ++i)
{
if (lookup[s[i] - 'a'].count == 0)
{
++uniq_count;
lookup[s[i] - 'a'].character = s[i];
}
++lookup[s[i] - 'a'].count;
if (max_count < lookup[s[i] - 'a'].count)
max_count = lookup[s[i] - 'a'].count;
}
if (max_count >= (len + 1) / 2)
return false;
std::sort(lookup.begin(), lookup.end(), [](const CharData &l, const CharData &r){return l.count > r.count;});
lookup.resize(uniq_count);
int s_idx = 0;
int lookup_idx_b = 0;
int lookup_idx_e = lookup.size() - 1;
while (s_idx < len)
{
if (!lookup[lookup_idx_b].count)
lookup_idx_b++;
if (!lookup[lookup_idx_e].count)
lookup_idx_e--;
if (lookup[lookup_idx_b].count)
{
s[s_idx++] = lookup[lookup_idx_b].character;
lookup[lookup_idx_b].count--;
}
if (lookup_idx_e > lookup_idx_b)
{
s[s_idx++] = lookup[lookup_idx_e].character;
lookup[lookup_idx_e].count--;
}
}
return true;
}
No need to sort, use backtracking to find the indx where the char repeats and replace with different char in the array if available, the following can be improved if memoized but its straight forward implementation
def fancy_shuffle(s):
s = list([a for a in s])
if len(s) == 0:
return False
currindx = None
currchar = None
i = 1
currchar = s[0]
while i < len(s):
if s[i] == currchar:
if currindx is None:
currindx = i
i += 1
else:
if currindx is not None:
t = s[i]
s[i] = s[currindx]
s[currindx] = t
currchar = t
i = currindx + 1
currindx = None
else:
currchar = s[i]
currindx = None
i += 1
if currindx is not None:
return False
print s
return True
I think we need a max-heap to store the character frequency. And we know the total count.
0. check the max frequency is no more than (total + 1) / 2
1. Every time we get the top 2 frequency(f1, f2), and then f1-1, f2-1, total - 2. Then put f1, f2 to the heap, go to 1.
just iterate is ok.
group all the repeating chars together.
return false if any of the group length is more then n/2(n being the string length)
start populating alternate positions with the grouped chars.
Eg:abbacddd
group it->aabbcddd
size of largest group = 3<n/2(n=8)
start populating the odd positions first.
a_a_b_b_
populate the remaining places.
acadbdbd.
Assuming the original question is accurate, I think this is a bit of a trick question.
There's no need to actually determine what the shuffled string is, only that a string can be 'fancy shuffled'. And that is true if the count of the most common character is less than or equal to (s.length +1) / 2. No string manipulation, no sorting.
Here's a complete solution in C#:
using System;
using System.Collections.Generic;
namespace FancyShuffle
{
class MainClass
{
public static void Main (string[] args)
{
Console.WriteLine("Fancy Shuffle");
Console.WriteLine("---");
Console.WriteLine("Can shuffle 'aa' : " + CanFancyShuffle("aa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ab' : " + CanFancyShuffle("ab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'aba' : " + CanFancyShuffle("aba".ToCharArray())); // True
Console.WriteLine("Can shuffle 'abaa' : " + CanFancyShuffle("abaa".ToCharArray())); // False
Console.WriteLine("Can shuffle 'abab' : " + CanFancyShuffle("abab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababa' : " + CanFancyShuffle("ababa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababaa' : " + CanFancyShuffle("ababaa".ToCharArray())); // False
Console.WriteLine("Can shuffle '' : " + CanFancyShuffle("".ToCharArray())); // True
}
static bool CanFancyShuffle(char[] s)
{
int highestCount = 0;
Dictionary<char, int> charCounts = new Dictionary<char, int> ();
foreach (char c in s)
{
if (charCounts.ContainsKey(c))
{
charCounts[c] = charCounts[c] + 1;
}
else
{
charCounts.Add(c, 1);
}
highestCount = Math.Max(highestCount, charCounts[c]);
}
return highestCount <= (s.Length + 1) / 2;
}
}
}
using System;
using System.Collections.Generic;
// This is a trick question. No need to actually determine the string, only to find if it _can_be shuffled or not.
// String can always be shuffled as long as the count of the most common character is <= (s.length + 1) / 2
namespace FancyShuffle
{
class MainClass
{
public static void Main (string[] args)
{
Console.WriteLine("Fancy Shuffle");
Console.WriteLine("---");
Console.WriteLine("Can shuffle 'aa' : " + CanFancyShuffle("aa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ab' : " + CanFancyShuffle("ab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'aba' : " + CanFancyShuffle("aba".ToCharArray())); // True
Console.WriteLine("Can shuffle 'abaa' : " + CanFancyShuffle("abaa".ToCharArray())); // False
Console.WriteLine("Can shuffle 'abab' : " + CanFancyShuffle("abab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababa' : " + CanFancyShuffle("ababa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababaa' : " + CanFancyShuffle("ababaa".ToCharArray())); // False
Console.WriteLine("Can shuffle '' : " + CanFancyShuffle("".ToCharArray())); // True
}
static bool CanFancyShuffle(char[] s)
{
int highestCount = 0;
Dictionary<char, int> charCounts = new Dictionary<char, int> ();
foreach (char c in s)
{
if (charCounts.ContainsKey(c))
{
charCounts[c] = charCounts[c] + 1;
}
else
{
charCounts.Add(c, 1);
}
highestCount = Math.Max(highestCount, charCounts[c]);
}
return highestCount <= (s.Length + 1) / 2;
}
}
}
using System;
using System.Collections.Generic;
// This is a trick question. No need to actually determine the string, only to find if it _can_be shuffled or not.
// String can always be shuffled as long as the count of the most common character is <= (s.length + 1) / 2
namespace FancyShuffle
{
class MainClass
{
public static void Main (string[] args)
{
Console.WriteLine("Fancy Shuffle");
Console.WriteLine("---");
Console.WriteLine("Can shuffle 'aa' : " + CanFancyShuffle("aa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ab' : " + CanFancyShuffle("ab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'aba' : " + CanFancyShuffle("aba".ToCharArray())); // True
Console.WriteLine("Can shuffle 'abaa' : " + CanFancyShuffle("abaa".ToCharArray())); // False
Console.WriteLine("Can shuffle 'abab' : " + CanFancyShuffle("abab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababa' : " + CanFancyShuffle("ababa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababaa' : " + CanFancyShuffle("ababaa".ToCharArray())); // False
Console.WriteLine("Can shuffle '' : " + CanFancyShuffle("".ToCharArray())); // True
}
static bool CanFancyShuffle(char[] s)
{
int highestCount = 0;
Dictionary<char, int> charCounts = new Dictionary<char, int> ();
foreach (char c in s)
{
if (charCounts.ContainsKey(c))
{
charCounts[c] = charCounts[c] + 1;
}
else
{
charCounts.Add(c, 1);
}
highestCount = Math.Max(highestCount, charCounts[c]);
}
return highestCount <= (s.Length + 1) / 2;
}
}
}
using System;
using System.Collections.Generic;
// This is a trick question. No need to actually determine the string, only to find if it _can_be shuffled or not.
// String can always be shuffled as long as the count of the most common character is <= (s.length + 1) / 2
namespace FancyShuffle
{
class MainClass
{
public static void Main (string[] args)
{
Console.WriteLine("Fancy Shuffle");
Console.WriteLine("---");
Console.WriteLine("Can shuffle 'aa' : " + CanFancyShuffle("aa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ab' : " + CanFancyShuffle("ab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'aba' : " + CanFancyShuffle("aba".ToCharArray())); // True
Console.WriteLine("Can shuffle 'abaa' : " + CanFancyShuffle("abaa".ToCharArray())); // False
Console.WriteLine("Can shuffle 'abab' : " + CanFancyShuffle("abab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababa' : " + CanFancyShuffle("ababa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababaa' : " + CanFancyShuffle("ababaa".ToCharArray())); // False
Console.WriteLine("Can shuffle '' : " + CanFancyShuffle("".ToCharArray())); // True
}
static bool CanFancyShuffle(char[] s)
{
int highestCount = 0;
Dictionary<char, int> charCounts = new Dictionary<char, int> ();
foreach (char c in s)
{
if (charCounts.ContainsKey(c))
{
charCounts[c] = charCounts[c] + 1;
}
else
{
charCounts.Add(c, 1);
}
highestCount = Math.Max(highestCount, charCounts[c]);
}
return highestCount <= (s.Length + 1) / 2;
}
}
}
I see this as constructing the truth table (roughly speaking)
Suppose we have AAAAAAAAA BBBB CC DDDDD E FFFF
We order it (as said before) by frequency:
A(9), D(5), B(4), F(4), C(2), E(1)
Then will construct the table starting with the most frequent char (in this case A). We fill it vertically, next we fill the second most frequent char and we continue with the remaining ones. example:
ADF
ADF
ADF
ADF
ADC
ABC
ABE
AB
AB
Now we concatenate all the lines of the table to have the required string:
ADFADFADFADFADCABCABEABAB
I don't have the mathematical proof for this, but as justification you can say, as long as you have a char that can be placed in the column next to the most frequent char you will be able to separate two similar chars.
Here is a C# example
- zsalloum April 10, 2015using System.IO; using System; using System.Text; using System.Collections.Generic; class Program { class Entry{ public char Ch; public int Freq; } static void Main() { String s = FancyShuffle("AAAAAABBBCCCDDDDDDDDDDFFFFF"); Console.WriteLine(s); } static String FancyShuffle(String s){ List<Entry> ls = ComputeFrequency(s); StringBuilder[] rows = new StringBuilder[ls[0].Freq]; int r = 0; for(int i = 0; i < ls.Count; i++){ Entry e = ls[i]; for(int k = 0; k < e.Freq; k++){ if(rows[r] == null) rows[r] = new StringBuilder(); rows[r].Append(e.Ch); r = (r + 1) % rows.Length; } } StringBuilder sb = new StringBuilder(); foreach(StringBuilder row in rows){ sb.Append(row); } return sb.ToString(); } static List<Entry> ComputeFrequency(String s){ Dictionary<char, Entry> dic = new Dictionary<char, Entry>(); for(int i = 0; i < s.Length; i++){ if(dic.ContainsKey(s[i])){ dic[s[i]].Freq += 1; }else{ Entry e = dic[s[i]] = new Entry(); e.Freq = 1; e.Ch = s[i]; } } List<Entry> lst = new List<Entry>(dic.Values); lst.Sort((e1, e2)=>{return e2.Freq - e1.Freq;}); return lst; } }