## Google Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

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

Let's check the examples again, as you see our string can shuffle when the maximum existed character in s is less than (the length of s + 1) / 2.
For examples:
apple => aplpe => valid
apppe => papep => valid
appp => invalid

My solution:
Time: O(n)
Mem: O(1)

``````public boolean canShuffle(char[] s) {
// initial counter array
int[] counter = new int[300];

// count the number of character in s
for (char c : s) {
counter[c]++;
}

// get the maximum from counter
int maxExistedCharacter = 0;
for (char c = 'a'; c <= 'z'; c++) {
maxExistedCharacter = Math.max(counter[c], maxExistedCharacter);
}

// s can shuffle when the maxExistedCharacter
// less than (length of s + 1) / 2
return maxExistedCharacter <= (s.length + 1) / 2;
}``````

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

@elena I think aba is a valid input. (It can be obtained by shuffling first and the last a?). Not sure though.

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

Hi chenm, as I understand abaaca is invalid because there're two 'a' adjacent.

Hi elena.nur88, I don't understand why aba is invalid.

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

that's not O(1) space. Still cuurious if O(1) is possible though

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

That's not O(1) space. Curious if O(1) space implementation is possible though

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

that's not O(1) space. Curious if a constant space implementation is possible though

sorry for multiple replies

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

@vaibhav.deshu, @interviewiseasy.com
If 'aba' is not a valid shuffle of an input 'aba', you also need to add a check if an input string is single valid shuffle of itself. It also can be done in O(N) though.

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

Seems like a trivial brain teaser

1. character w/ highest repeat count has n - 1 holes to fill where n is the repeat count.
2. all subsequent repeats and singles must be able to fill n-1 holes. This means sum of remaining repeats + singles need to be at least n - 1.
a. If sum < n -1, that means it's not possible to form a string without neighboring repeats.
b. If sum >= n -1, it's possible to form a string with neighboring repeats

Note that >= relation in 2.b is true because you can stuff > 1 character per hole.

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NewNamespace
{
class ShuffleString
{
public int num;
public void ShuffleStringInput(string str)
{
char[] mycharArray = str.ToCharArray();
int count = str.Length;

for (int i = 0; i < str.Length; i++ )
{
if (char.ToLower(mycharArray[0]) == char.ToLower(mycharArray[i]))
{
num++;
if (num == count)
{

Console.WriteLine("They can not shuffle");
break;
}

}
else
{

Console.WriteLine("We can shuffle this string");
break;
}
}
}

}

class Program
{
static void Main(string[] args)
{
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);

}

}

}

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NewNamespace
{
class ShuffleString
{
public int num;
public void ShuffleStringInput(string str)
{
char[] mycharArray = str.ToCharArray();
int count = str.Length;

for (int i = 0; i < str.Length; i++ )
{
if (char.ToLower(mycharArray[0]) == char.ToLower(mycharArray[i]))
{
num++;
if (num == count)
{

Console.WriteLine("They can not shuffle");
break;
}

}
else
{

Console.WriteLine("We can shuffle this string");
break;
}
}
}

}

class Program
{
static void Main(string[] args)
{
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);

}

}

}``````

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NewNamespace
{
class ShuffleString
{
public int num;
public void ShuffleStringInput(string str)
{
char[] mycharArray = str.ToCharArray();
int count = str.Length;

for (int i = 0; i < str.Length; i++ )
{
if (char.ToLower(mycharArray[0]) == char.ToLower(mycharArray[i]))
{
num++;
if (num == count)
{

Console.WriteLine("They can not shuffle");
break;
}

}
else
{

Console.WriteLine("We can shuffle this string");
break;
}
}
}

}

class Program
{
static void Main(string[] args)
{
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);

}

}

}

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace NewNamespace
{
class ShuffleString
{
public int num;
public void ShuffleStringInput(string str)
{
char[] mycharArray = str.ToCharArray();
int count = str.Length;
for (int i = 0; i < str.Length; i++ )
{
if (char.ToLower(mycharArray[0]) == char.ToLower(mycharArray[i]))
{
num++;
if (num == count)
{
Console.WriteLine("They can not shuffle");
break;
}
}
else
{
Console.WriteLine("We can shuffle this string");
break;
}
}
}
} class Program
{
static void Main(string[] args)
{
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);
}

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace NewNamespace
{    class ShuffleStrin   {
public int num;
public void ShuffleStringInput(string str)
{
char[] mycharArray = str.ToCharArray();
int count = str.Length;

for (int i = 0; i < str.Length; i++ )
{
if (char.ToLower(mycharArray[0]) == char.ToLower(mycharArray[i]))
{
num++;
if (num == count)
{
Console.WriteLine("They can not shuffle");
break;}}
else
{
Console.WriteLine("We can shuffle this string");
break;``````

}
class Program{
static void Main(string[] args)
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);

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

String has invalid shuffle in case there are dublicates more that n/2 for even string length and n/2 + 1 for odd ones

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

An implementation to back up my statement above

``````boolean isValidShuffle(String apple) {
if(apple.length() <= 1)
return true;
int[] freq = new int[26];
int max = Integer.MIN_VALUE;
for (char ch : apple.toCharArray())  {
freq[ch -'a'] ++;
if(max < freq[ch -'a']) {
max = freq[ch -'a'];
}
}
return (max > (apple.length()*1.0/2.0 + 0.5))? false: true;
}``````

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

refactored a little bit

``````boolean isValidShuffle(String apple) {
if(apple.length() <= 1)
return true;
int[] freq = new int[26];
int max = Integer.MIN_VALUE;
for (char ch : apple.toCharArray())  {
freq[ch -'a'] ++;
if(max < freq[ch -'a']) {
max = freq[ch -'a'];
}
}
return max > (apple.length()+ 1)/2? false: true;
}``````

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

#include<stdio.h>
#include<string.h>
//int partition(char * ,int ,int);
void bubble(char *, int );

int main()
{
int i;

char str[100];
char str1[100];
printf("\nENTER THE FIRST STRING:=>");
gets(str);
printf("\n ENTER THE SECOND STRING:=>");
gets(str1);

bubble(str,strlen(str));
bubble(str1,strlen(str1));
printf("%d",strlen(str));
printf("SORTED first ARRAY:=>");
for(i=0;i<strlen(str);i++)
printf("%c->",str[i]);

printf("\n SORTED second ARRAY:=>");
for(i=0;i<strlen(str1);i++)
printf("%c->",str1[i]);

if(strcmp(str1,str)==0)
printf("IMPOSSIBLE");

else
{

for(i=0;i<strlen(str);i++)
{
if(str[i]==str1[i])
continue;
else
{
printf("invalid string");
break;
}
}

}

return 0;
}

void bubble(char *a,int size)
{
int i,j;
char temp;

for(i=0;i<size-1;i++)
{
for(j=0;j<size-1-i;j++)
{

if(a[j]>a[j+1])
{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}

}
}

}

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

O(1) space and O(n) time

``````public static boolean checkStringCanShuffle(String input){
int[] score = new int[256];
int maxScore = 0;
for(char c : input.toCharArray()){
score[c] = score[c]+1;
maxScore = Math.max(maxScore, score[c]);
}
if(input.length()%2==0){
return (maxScore)<(input.length()/2)+1;
}else{
return (maxScore)<=(input.length()/2)+1;
}

}``````

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

Python:

``````def isValidShuffle( s ):

d = {}
max_exist_char_ct = 0
max_exist_char = ""

for v in s:
if d.has_key(v):
d[v] += 1

#update dictionary
if d[v] > max_exist_char_ct:
max_exist_char_ct = d[v]
max_exist_char = v

#check condition
if len(s) < 2 * d[max_exist_char] - 1:
return False
else:
d[v] = 1

return True``````

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

We can shuffle if there are (maximum existente character minus one) available characters is S; s.Length - maxRepeated >= maxRepeated - 1;

Exe. aaaabbc Maxrepeated = 4 so we need 3 available characters in S in order to shuffle: ababaca

``````public bool CanShuffle(string s)
{
var dict = new Dictionary<char, int>();
int maxRepeated = int.MinValue;

foreach (char c in s)
{

int n = 0;
if (!dict.TryGetValue(c, out n))
else
dict[c] = n + 1;

maxRepeated = Math.Max(maxRepeated, dict[c]);
}

return s.Length - maxRepeated >= maxRepeated - 1;
}``````

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

``````package src;
import java.util.HashMap;
public static void main(String args[]) {
for (String problem : args)
{
HashMap<Character, Integer> charMap = new HashMap<Character, Integer>();
int maxRepeatingCharNumber = 0;
for (Character pch : problem.toCharArray())
{
if(charMap.isEmpty())
{
charMap.put(pch, 1);
maxRepeatingCharNumber++;
}
else if (charMap.containsKey(pch))
{
int pchNewCount = (charMap.get(pch) + 1);
charMap.put(pch, pchNewCount);
if (pchNewCount > maxRepeatingCharNumber)
maxRepeatingCharNumber = pchNewCount;
}
else
charMap.put(pch, 1);
}
if (((2*maxRepeatingCharNumber) - 1) > problem.length())
System.out.println("Poblem Word --> " + problem + " --> Invalid");
else
System.out.println("Poblem Word --> " + problem + " --> Valid");
}
}
}``````

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

``````import java.util.TreeMap;

public class StringShufle {

public boolean canSuffled(String str){

TreeMap<Character, Integer> stirngHistogramOrdered = new TreeMap<>();
for(int i=0;i<str.length();i++){
int count = 1;
if(stirngHistogramOrdered.get(str.charAt(i))!=null){
count =  stirngHistogramOrdered.get(str.charAt(i))+1;
}
stirngHistogramOrdered.put(str.charAt(i),count);
}
Integer[] histogramValues = stirngHistogramOrdered.values().toArray(new Integer[stirngHistogramOrdered.size()]);
int dif=0;

for(int i=0;i<histogramValues.length;i++){
dif = Math.abs(dif-histogramValues[i]);
}
if(dif>1){
return false;
}

return true;
}

public static void main(String[] args){
StringShufle stringShufle = new StringShufle();
System.out.println("can shuffle?:"+stringShufle.canSuffled("aavcdw"));
}

/*    apple >> alpep, so valid
a >> a, valid
aa >> aa, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid*/
}``````

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

``````public static boolean stringShuffle(String s){
Hashtable <Character,Integer> charCount = new Hashtable<Character,Integer>();
int maxCount = 0;
int stringLength = s.length();
for(int i= 0;i<stringLength;i++){
if(charCount.keySet().contains(s.charAt(i))){
charCount.put(s.charAt(i), charCount.get(s.charAt(i))+1);
}
else{
charCount.put(s.charAt(i), 1);
}
int currCount = charCount.get(s.charAt(i));
System.out.println(maxCount);
if(currCount>maxCount)maxCount = currCount;
if(stringLength %2==0)if(maxCount>stringLength/2)return false;
else if(maxCount>stringLength/2+1)return false;
}

return true;
}``````

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

``````public static boolean stringShuffle(String s){
Hashtable <Character,Integer> charCount = new Hashtable<Character,Integer>();
int maxCount = 0;
int stringLength = s.length();
for(int i= 0;i<stringLength;i++){
if(charCount.keySet().contains(s.charAt(i))){
charCount.put(s.charAt(i), charCount.get(s.charAt(i))+1);
}
else{
charCount.put(s.charAt(i), 1);
}
int currCount = charCount.get(s.charAt(i));
System.out.println(maxCount);
if(currCount>maxCount)maxCount = currCount;
if(stringLength %2==0)if(maxCount>stringLength/2)return false;
else if(maxCount>stringLength/2+1)return false;
}

return true;
}``````

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

``````bool CanShuffleWithoutRepeat(string& str)
{
map<char, size_t> repeats;
size_t max = 0;
for (string::iterator it = str.begin(); it != str.end(); it++) {
if (repeats.find(*it) == repeats.end())
repeats.emplace(*it, 1);
else
repeats[*it]++;
max = Max(max, repeats[*it]);
}
return str.size() - max >= max - 1;
}``````

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

The intuition here is that if most frequent character in string occurs n times, the string length should be at least 2*n-1 to keep these n similar characters apart.

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

``````def shuffle_without_dup(s):
d = {}
for c in s:
d[c] = d[c] + 1 if c in d else 1
check = max(d.values())
return check * 2 - 2 < len(s)

assert shuffle_without_dup('apple')
assert shuffle_without_dup('a')
assert not shuffle_without_dup('aa')
assert shuffle_without_dup('aab')
assert shuffle_without_dup('aaaabbcc')``````

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

``````bool canShuffle(string str) {
int maxCharCount = (str.size()+1)/2;
int charCount[256] = {0};

for(char c : str) {
if(++charCount[c] >= maxCharCount)
return false;
}
return true;
}``````

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

``````bool canShuffle(string str) {
int maxCharCount = (str.size()+1)/2;
int charCount[256] = {0};

for(char c : str) {
if(++charCount[c] >= maxCharCount)
return false;
}
return true;
}``````

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

Statement: We can shuffle the string if and only if the frequency of maximum occurring charterer is less than or equals len(string) + 1.

Proof. Let's consider we have a string of length 9. In worst case the valid shuffle should be looks like:
X_X_X_X_X_X where X is the max occurring char.

so for string having length of 9, we can almost 5 most occurring char. If we add one then it will break the above structure having a distinct char in-between two same char.

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.

### 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.