## Google Interview Question for Software Engineers

• 0
of 0 votes

Country: India
Interview Type: Phone Interview

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

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

``````using 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.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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.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)
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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont see this working for something like "aaaabbbcc"

Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think it won't work for AAAAABCDE, which can be written as ABACADAEA

Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Anonymous It would work. abababcac
@ Anil. Number of A is 5. 5 > (9+1)/2 = 5 is false. So, the function will return true.

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

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.join("");
};

console.log(module.exports('aaaaabbbbcccceeeeeeeeeeddddffghijkl'))

//output
'eaedecefeaebeceheaedclabckadfbjdgbi'``````

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

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep, that's my solution too. Except for 5 the check is against (n+1)/2

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

special check/arrangement needed when two chars have same (highest) count at every iteration in step 3.

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

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);
}

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

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);
}

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

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);
}

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

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);
}

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

---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);
}

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

---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);
}

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

---adding the check for possibility
boolean fancy_shuffle(s: string)
{
.
.
.
if length(s)>0
return WriteTheNewString(a, m, length(s));
}

WriteTheNewString(a, m, l)
{
// l is how much chars remained to get printed
if l = 0 return 0;
.
.
.
if pos==-1 return -1;
write(char(a[i]));
.
.
.
}

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

---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);
}

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

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))

Comment hidden because of low score. Click to expand.
0
of 0 votes

Can be done in O(n) without need for sorting, only finding max is required. See the solution below

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

``````# 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, 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] == 0):
k += 1
inStr [i] = tempArray[k]
tempArray[k] -= 1
i += 2

i = 1
while ((i < totalCount) and (k < tempArrayLen)):
if (tempArray[k] == 0):
k += 1
inStr [i] = tempArray[k]
tempArray[k] -= 1
i += 2
return True

def fancyShuffle_Check (tempArray):
maxCharCount = tempArray
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)``````

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

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] > 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 for x in range(tuple)])
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")``````

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

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();
}``````

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

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

"aabbbbcc" will fail on your algo: it will return "ababbcbc"

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

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)

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

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;
}

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

``````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;
}``````

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

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
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``````

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

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, "go to 1" should be "go to 0"

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

what if you get
AAABBBB
you will get to
ABABAB
and then where you put the last B

Comment hidden because of low score. Click to expand.
0
of 0 votes

the largest group can be at max N/2 + 1

Comment hidden because of low score. Click to expand.
0
of 0 votes

Have to start with the highest number of times repeated character , place it to the odd positions first , then start with other numbers to fill in between by picking the numbers in decreasing order of their repetition.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

This needs to re-arrange the characters in the Fancy Shuffle.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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;
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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;
}
}
}``````

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