Google Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
@elena I think aba is a valid input. (It can be obtained by shuffling first and the last a?). Not sure though.
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.
that's not O(1) space. Curious if a constant space implementation is possible though
sorry for multiple replies
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.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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)
{
Console.WriteLine("Please enter your string : ");
string value = Console.ReadLine();
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);
Console.ReadKey();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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)
{
Console.WriteLine("Please enter your string : ");
string value = Console.ReadLine();
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);
Console.ReadKey();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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)
{
Console.WriteLine("Please enter your string : ");
string value = Console.ReadLine();
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);
Console.ReadKey();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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)
{
Console.WriteLine("Please enter your string : ");
string value = Console.ReadLine();
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);
Console.ReadKey();} }
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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)
{Console.WriteLine("Please enter your string : ");
string value = Console.ReadLine();
ShuffleString s = new ShuffleString();
s.ShuffleStringInput(value);
Console.ReadKey();
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;
}
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;
}
#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;
}
}
}
}
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;
}
}
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
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))
dict.Add(c, 1);
else
dict[c] = n + 1;
maxRepeated = Math.Max(maxRepeated, dict[c]);
}
return s.Length - maxRepeated >= maxRepeated - 1;
}
package src;
import java.util.HashMap;
public class GoogleContinuousWordProb {
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");
}
}
}
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*/
}
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;
}
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;
}
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;
}
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')
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.
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)
- techinterviewquestion.com February 12, 2016public 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; }