VMWare Inc Interview Question
MTSsCountry: United States
Interview Type: In-Person
public static void start()
{
string inputStr = "aaabb";
Console.WriteLine(inputStr + " = " + cutString(inputStr));
inputStr = "aaabbbb";
Console.WriteLine(inputStr + " = " + cutString(inputStr));
inputStr = "aaabbb";
Console.WriteLine(inputStr + " = " + cutString(inputStr));
inputStr = "aabbbbbb";
Console.WriteLine(inputStr + " = " + cutString(inputStr));
inputStr = "aabbbba";
Console.WriteLine(inputStr + " = " + cutString(inputStr));
}
public static bool cutString(string inputStr)
{
Dictionary<char, int> charCount = countChars(inputStr);
// TODO: Make sure the charCount.keys == 2
char char1 = charCount.Keys.First();
char char2 = charCount.Keys.Last();
if (charCount[char1] == charCount[char2]) {return true; }
// Figure out which one to remove, and how many
char toRemove;
int removeCount;
if (charCount[char1] > charCount[char2])
{
toRemove = char1;
removeCount = charCount[char1] - charCount[char2];
}
else
{
toRemove = char2;
removeCount = charCount[char2] - charCount[char1];
}
// Start cutting from left
int leftCount = findRepeat(inputStr, toRemove, true);
if (leftCount >= removeCount) { return true; }
// Try cutting from right, but substract first
removeCount -= leftCount;
int rightCount = findRepeat(inputStr, toRemove, false);
if (rightCount >= removeCount) { return true; }
return false;
}
private static int findRepeat(string inputStr, char toFind, bool leftToRight)
{
int numOfRepeat = 0;
char[] inputChars = inputStr.ToCharArray();
if (!leftToRight) { inputChars = inputChars.Reverse().ToArray(); }
for (int i = 0; i < inputStr.Length; i++)
{
if (inputChars[i] != toFind) { break; }
numOfRepeat++;
}
return numOfRepeat;
}
private static Dictionary<char, int> countChars(string inputStr)
{
Dictionary<char, int> charCount = new Dictionary<char, int>();
foreach (char chr in inputStr)
{
int count = 0;
if (charCount.ContainsKey(chr))
{
count = charCount[chr];
charCount.Remove(chr);
}
charCount.Add(chr, ++count);
}
return charCount;
}
def find_cut_point(some_string){
counter = 0
a_counter_list = list( some_string.toCharArray ) as {
// cumulative count of 'a' at index
( $.o == _'a' ) ? ( counter += 1 ) : counter
}
N = size(some_string)
A_count = a_counter_list[-1]
B_count = N - A_count
exists( a_counter_list ) where {
// $.o is the current item
// $.i is the index of the item
current_b_count = $.i + 1 - $.o
count_a_which_will_be_left = A_count - $.o
count_b_which_will_be_left = B_count - current_b_count
count_a_which_will_be_left == count_b_which_will_be_left
}
}
find_cut_point( "aaabbb" )
let dp[i][j]=frequency of jth character(in ascii) till the ith index.
example: "aabc"
dp[0]['a']=1
dp[2]['a']=2
dp[2]['b']=1
dp[3]['a']=2
dp[3]['b']=1
dp[3]['c']=1
N=length of String
int ans;
for(int i=0;i<N;i++){
ans=i;
for(int j=1;j<255;j++){
if(dp[i][j]!=dp[N-1][j]-dp[i][j]){
ans=-1;
break;
}
}
if(ans!=-1)break;
}
return ans;
///Also works for string like "aabacabab" and "aabacaabbccdd"
public static bool SameFrequencyCharacters(string input)
{
var charFrequency = new Dictionary<char, int>();
for (int i = 0; i < input.Length; i++)
{
FillDictionary(charFrequency, input, i);
var matchFound = ValidateData(charFrequency);
if (matchFound)
{
return true;
}
}
var reverseCharFrequency = new Dictionary<char, int>();
for (int i = input.Length - 1; i >= 0; i--)
{
FillDictionary(reverseCharFrequency, input, i);
var matchFound = ValidateData(reverseCharFrequency);
if (matchFound)
{
return true;
}
}
return false;
}
public static bool ValidateData(Dictionary<char, int> charFrequency)
{
if (charFrequency.Count < 2)
{
return false;
}
int prevCount = 0;
foreach (var element in charFrequency)
{
prevCount = element.Value;
break;
}
foreach (var element in charFrequency)
{
if (element.Value != prevCount)
{
return false;
}
}
return true;
}
public static void FillDictionary(Dictionary<char, int> frequencyData, string input, int counter)
{
if (frequencyData.ContainsKey(input[counter]))
{
frequencyData[input[counter]] = frequencyData[input[counter]] + 1;
}
else
{
frequencyData.Add(input[counter], 1);
}
}
public static boolean sameFrequencyCharactersInString(String str) {
HashMap<Character,Integer> map = new HashMap();
for(int i =0; i< str.length(); i++) {
map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0)+1);
}
Set<Integer> values = new HashSet<Integer>();
for (Integer value : map.values()) {
if (!values.add(value)) {
return true;
}
}
return false;
}
public static boolean sameFrequencyCharactersInString(String str) {
HashMap<Character,Integer> map = new HashMap();
for(int i =0; i< str.length(); i++) {
map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0)+1);
}
Set<Integer> values = new HashSet<Integer>();
for (Integer value : map.values()) {
if (!values.add(value)) {
return true;
}
}
return false;
}
if the strings will be as per questions -> all the 'a's will be on left and all the 'b's on the right:
bool cutString(std::string str)
{
if (str.length() <= 1 || (str.length()%2 ==1))
{
return false;
}
int countaleft = 0, countbright = 0;
int length = int(str.length());
for (int i = 0; i < length/ 2; ++i)
{
if (str[length - i - 1] == 'b')
++countbright;
else
return false;
if (str[i] == 'a')
++countaleft;
else
return false
}
return (countaleft == countbright);
}
if string passed has jumbled 'a's and 'b's only then 2 more counts can be added countaright and countbleft
if string passed can have every alphabet then 2 maps of 26 counts each for every character and at the end just compare each count , one mismatch and return false.
// Complete the isValid function below.
static String isValid(String s) {
int[] letterCounts = preProcessInput(s);
if(letterCounts == null) return "NO";
//navigate array and check if all except one letter has the same count
//more than 1 letter has different count return NO
//one letter has different count but more than 1 then return NO
//else return YES
Arrays.sort(letterCounts);
int i = 0;
while(letterCounts[i] == 0) {
//skip all 0 counts
i++;
}
int minCount = letterCounts[i];
int maxCount = letterCounts[letterCounts.length-1];
if(maxCount - minCount == 0) return "YES";
//difference should be 1 and if so the count next to min should be less than max count
if(maxCount - minCount == 1 && letterCounts[letterCounts.length-2] < maxCount) return "YES";
//difference is not 1 so check if min is 1 and if so the count next to min must be the same as max
if(minCount == 1 && letterCounts[i+1] == maxCount) return "YES";
return "NO";
}
private static int[] preProcessInput(String s) {
if(s == null || s.isEmpty()) return null;
int[] letterCounts = new int[26];
for(char c : s.toCharArray()) {
int index = c - 'a';
letterCounts[index]++;
}
return letterCounts;
}
the delimiter is the combination of ab, it's literally just a split and count what's left in each array element. Doesn't matter that the Split removes the ab, as it's 1 being removed from both sides of the array.
string a = "aaabb";
string b = "aaabbbb";
string c = "aaabbb";
var array = new string[] {a, b, c};
foreach (var item in array)
{
var splitItem = item.Split("ab");
if(splitItem[0].Length == splitItem[1].Length)
Console.WriteLine("True");
else
Console.WriteLine("False");
}
- Shalini July 26, 2019