Google Interview Question
Software EngineersCountry: India
Interview Type: Phone Interview
Consider first a complete search approach, generate all strings of length N with chars from A-Z, then for each of them, compute it's foo value in O(N) time and compare against K. Since there are 26^N such strings, time complexity of complete search is O(N 26^N) which is pretty slow.
Can we do better?
Note that consonants are not considered for the foo value of a string, so represent any of them by using the star symbol *. Generate all strings of length N where chars can be a vowel or a star *, then for each of them, compute it's foo value in O(N), if it equals K, then count the stars in the string and add 21^starsCount to the solution. Given that there are 6^N such strings time complexity is reduced to O(N 6^N), great!
Can we do better?
We can remove the N factor as follows, keep track of 'foo' and 'stars' as we build the strings, foo = 0 and stars = 0 at the beginning. If at step i, 0 <= i < N, pass stars + 1 to the recursive call if extending the current string with a *, or if i > 0 and last char is a vowel and extending the string with that same char for the next step, pass foo + 1 to the recursive call. Doing this reduces the need to run thru the string when we reach step N, so time complexity goes down to O(6^N).
Also knowing that value of foo as we build the solution enables us to backtrack. If at some point foo = K, we can avoid extending with a char that would increase foo. Also if we are at step i, there are N - i remaining steps, if foo = F and K - F > N - i, we can tell it's not possible to make foo = K by extending current path and return early.
Can we do better?
We can see that in the recursion, what determines what the solution following that path will be are: the last selected char (6 possible values), the step number i (N + 1 possible values), and the running value of foo (K + 1 possible values) and starts (N + 1 possible values). It's easy to see that there are 6 * (N + 1) * (K + 1) * (N + 1) different possible states we can be in while doing the recursion, that's O(K N^2). By using dynamic programming to memoize answer for the states we already know the solution for, complexity becomes O(K N^2) for both time and extra space.
Count(..., true) is the branch when we use a vowel.
Count(..., false) is the branch when we don't use a vowel.
In the first case, depending on if the previous was a vowel, we decrement k or we don't.
I refactored it into this (though, functionally it's the same thing):
uint64_t count =
Count(n - 1, prev_is_vowel ? k - 1 : k, memo, true) +
Count(n - 1, k, memo, false);
Recursive approach -
public static void main(String[] args) {
int N = 5;
int K = 2;
System.out.println(count(N, K, K, 1, 1, 0));
}
// N=5, K= 2
public static int count(int N, int K, int k, int p, int count, int total) {
for (int i = p; i <= N; i++) {
if(K > 0 && i + 1 <= N) {
total = count(N, K - 1, k, i + 2, count*5, total);
}
if (i <= N) {
count *= 26;
}
}
if (K == 0){
total += count;
}
return total;
}
A simple DP solution
int num_c1(int N1, int M1, int t1)
{
if (N1 == 0)
return 0;
if (N1 == 1 && M1 == 0)
if (t1 == 0)
return 21;
else
return 5;
if (t1 == 0)
return num_c1(N1 - 1, M1, 0) * 21 + num_c1(N1 - 1, M1, 1) * 25;
if (t1 == 1)
return num_c1(N1 - 1, M1 - 1, 1) + num_c1(N1 - 1, M1, 0) * 5;
if (t1 == 2)
return num_c1(N1 - 1, M1, 0) * 21 + num_c1(N1 - 1, M1, 1) * 25 + num_c1(N1 - 1, M1 - 1, 1) + num_c1(N1 - 1, M1, 0) * 5;
}
int main()
{
cout << num_c1(1, 1, 2) << endl;
cout << num_c1(3, 1, 2) << endl;
cout << num_c1(3, 2, 2) << endl;
cout << num_c1(4, 2, 2) << endl;
cout << num_c1(4, 3, 2) << endl;
return 0;
}
Here is a slightly improved version without cutoffs hopefully
// vowel set.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
#include <stdint.h>
bool is_vowel(char c)
{
return c == 'A' ||
c == 'E' ||
c == 'I' ||
c == 'O' ||
c == 'U' ||
c == 'a' ||
c == 'e' ||
c == 'i' ||
c == 'o' ||
c == 'u';
}
int count(char *s)
{
int c = 0;
int state = 0;
int i = 0;
while(s[i] != 0)
{
switch (state)
{
case 0: // last letter was con
if (is_vowel(s[i]))
{
state = 1;
}
break;
case 1: // last was vowle
if (is_vowel(s[i]))
{
if (s[i - 1] == s[i])
{
c++;
state = 2;
}
}
else
{
state = 0;
}
break;
case 2: // in a sequence
if (is_vowel(s[i]))
{
if (s[i - 1] != s[i])
{
state = 1;
}
}
else
{
state = 0;
}
break;
}
i++;
}
return c;
} //----------------------------------------------------------------------------------------------------------------
int test_all_string_r(int n, int k, char *s, int l)
{
if (l == n)
{
//cout << s;
int x = count(s);
if (x == k)
{
//cout << " *\n";
return 1;
}
else
{
//cout << "\n";
return 0;
}
}
int sum = 0;
for (char c = 'A'; c <= 'Z'; c++)
{
s[l] = c;
sum = sum + test_all_string_r(n, k, s, l + 1);
}
return sum;
}//----------------------------------------------------------------------------------------------------------------
int test_all_string(int n, int k)
{
char *s = new char[n + 1];
s[n] = 0;
int out = test_all_string_r(n, k, s, 0);
delete[] s;
return out;
}//----------------------------------------------------------------------------------------------------------------
void dump(const vector<vector<uint64_t>> &in)
{
for (int y = 0; y < in[0].size(); y++)
{
for (int x = 0; x < in.size(); x++)
{
cout << in[x][y] << " ";
}
cout << "\n";
}
}
uint64_t dp_cont_2(int n, int k) // n > 1 and k > 0
{
vector<vector<uint64_t>> end_consonant(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_vowel_set(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_single_vowel(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> total(n + 1, vector<uint64_t>(k + 1, 0));
end_consonant[1][0] = 26 - 5; // any of the consonants
end_single_vowel[1][0] = 5; // any of the vowels
total[1][0] = 26;
for (int ni = 2; ni <= n; ni++)
{
for (int ki = 0; ki <= k; ki++)
{
end_consonant[ni][ki] = total[ni - 1][ki] * (26 - 5);
// ways of doing it with one less letter and then we add a new consonant at the end
uint64_t ec = end_consonant[ni][ki];
end_single_vowel[ni][ki] = end_single_vowel[ni - 1][ki] * 4 + // add a different vowel
end_vowel_set[ni - 1][ki] * 4 + // add a different vowel
end_consonant[ni - 1][ki] * 5; // add any vowel
uint64_t esv = end_single_vowel[ni][ki];
if (ki > 0)
{
uint64_t d = end_single_vowel[ni - 1][ki - 1];
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki] + d;
}
else
{
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki];
}
uint64_t evs = end_vowel_set[ni][ki];
total[ni][ki] = end_consonant[ni][ki] +
end_vowel_set[ni][ki] +
end_single_vowel[ni][ki]; // total ways with one less letter
uint64_t t = total[ni][ki];
}
}
cout << "--------end_consonant---------------------------------------\n";
dump(end_consonant);
cout << "--------end_vowel_set---------------------------------------\n";
dump(end_vowel_set);
cout << "--------end_single_vowel---------------------------------------\n";
dump(end_single_vowel);
cout << "--------total---------------------------------------\n";
dump(total);
cout << "-----------------------------------------------\n";
return total[n][k];
}
int _tmain(int argc, _TCHAR* argv[])
{
cout << "(1, 0) " << test_all_string(1, 0) << '\n';
cout << "(1, 1) " << test_all_string(1, 1) << '\n';
cout << "(2, 0) " << test_all_string(2, 0) << '\n';
cout << "(2, 1) " << test_all_string(2, 1) << '\n';
cout << "(3, 1) " << test_all_string(3, 1) << '\n';
cout << "(4, 2) " << test_all_string(4, 2) << '\n';
cout << "(5, 2) " << test_all_string(5, 2) << '\n';
cout << dp_cont_2(5, 2);
return 0;
}
public class FooCount {
public static void main(String[] args) {
// TODO Auto-generated method stub
int strLength = 5;
int foolength = 3;
int value =0;
for(int i=1; i<=strLength; i++) {
if(i>=foolength) {
int CombCount = strLength-(i-1);
value = value + (i-(foolength-1))*CombCount;
}
}
System.out.println("the favoriye combinations:"+ value);
}
}
"public class FooCount {
public static void main(String[] args) {
// TODO Auto-generated method stub
int strLength = 5;
int foolength = 3;
int value =0;
for(int i=1; i<=strLength; i++) {
if(i>=foolength) {
int CombCount = strLength-(i-1);
value = value + (i-(foolength-1))*CombCount;
}
}
System.out.println("the favoriye combinations:"+ value);
}
}"
public class FooCount {
public static void main(String[] args) {
// TODO Auto-generated method stub
int strLength = 5;
int foolength = 3;
int value =0;
for(int i=1; i<=strLength; i++) {
if(i>=foolength) {
int CombCount = strLength-(i-1);
value = value + (i-(foolength-1))*CombCount;
}
}
System.out.println("the favoriye combinations:"+ value);
}
}
public class FooCount {
public static void main(String[] args) {
// TODO Auto-generated method stub
int strLength = 5;
int foolength = 3;
int value =0;
for(int i=1; i<=strLength; i++) {
if(i>=foolength) {
int CombCount = strLength-(i-1);
value = value + (i-(foolength-1))*CombCount;
}
}
System.out.println("the favoriye combinations:"+ value);
}
}
Here is a dp solution and a brute force solution. You can improve the DP solution by removing the total array and reducing the other matrices to a pair of vectors that you swap on every cycle.
#include <iostream>
#include <vector>
using namespace std;
#include <stdint.h>
int count(char *s)
{
int c = 0;
int state = 0;
int i = 0;
while(s[i] != 0)
{
switch (state)
{
case 0: // last letter was con
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
state = 1;
}
break;
case 1: // last was vowle
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
if (s[i - 1] == s[i])
{
c++;
state = 2;
}
}
else
{
state = 0;
}
break;
case 2: // in a sequence
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
if (s[i - 1] != s[i])
{
state = 1;
}
}
else
{
state = 0;
}
break;
}
i++;
}
return c;
} //----------------------------------------------------------------------------------------------------------------
int test_all_string_r(int n, int k, char *s, int l)
{
if (l == n)
{
//cout << s;
int x = count(s);
if (x == k)
{
//cout << " *\n";
return 1;
}
else
{
//cout << "\n";
return 0;
}
}
int sum = 0;
for (char c = 'A'; c <= 'Z'; c++)
{
s[l] = c;
sum = sum + test_all_string_r(n, k, s, l + 1);
}
return sum;
}//----------------------------------------------------------------------------------------------------------------
int test_all_string(int n, int k)
{
char *s = new char[n + 1];
s[n] = 0;
int out = test_all_string_r(n, k, s, 0);
delete[] s;
return out;
}//----------------------------------------------------------------------------------------------------------------
void dump(const vector<vector<uint64_t>> &in)
{
for (int y = 0; y < in[0].size(); y++)
{
for (int x = 0; x < in.size(); x++)
{
cout << in[x][y] << " ";
}
cout << "\n";
}
}
uint64_t dp_cont_2(int n, int k) // n > 1 and k > 0
{
vector<vector<uint64_t>> end_consonant(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_vowel_set(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_single_vowel(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> total(n + 1, vector<uint64_t>(k + 1, 0));
end_consonant[1][0] = 26 - 5; // any of the consonants
end_single_vowel[1][0] = 5; // any of the vowels
total[1][0] = 26;
for (int ni = 2; ni <= n; ni++)
{
for (int ki = 0; ki <= k; ki++)
{
end_consonant[ni][ki] = total[ni - 1][ki] * (26 - 5); // ways of doing it with one less letter and then we add a new consonant at the end
uint64_t ec = end_consonant[ni][ki];
end_single_vowel[ni][ki] = end_single_vowel[ni - 1][ki] * 4 + // add a different vowel
end_vowel_set[ni - 1][ki] * 4 + // add a different vowel
end_consonant[ni - 1][ki] * 5; // add any vowel
uint64_t esv = end_single_vowel[ni][ki];
if (ki > 0)
{
uint64_t d = end_single_vowel[ni - 1][ki - 1];
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki] + d;
}
else
{
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki];
}
end_vowel_set[ni][ki] = ((ki > 0) ? end_single_vowel[ni - 1][ki - 1] : 0) + // k went up so we need to have i-1
end_vowel_set[ni - 1][ki]; // add a vowel after eithe a uneque v and a set of vs
uint64_t evs = end_vowel_set[ni][ki];
total[ni][ki] = end_consonant[ni][ki] + end_vowel_set[ni][ki] + end_single_vowel[ni][ki]; // total ways with one less letter
uint64_t t = total[ni][ki];
}
}
cout << "--------end_consonant---------------------------------------\n";
dump(end_consonant);
cout << "--------end_vowel_set---------------------------------------\n";
dump(end_vowel_set);
cout << "--------end_single_vowel---------------------------------------\n";
dump(end_single_vowel);
cout << "--------total---------------------------------------\n";
dump(total);
cout << "-----------------------------------------------\n";
return total[n][k];
}
int _tmain(int argc, _TCHAR* argv[])
{
cout << "(1, 0) " << test_all_string(1, 0) << '\n';
cout << "(1, 1) " << test_all_string(1, 1) << '\n';
cout << "(2, 0) " << test_all_string(2, 0) << '\n';
cout << "(2, 1) " << test_all_string(2, 1) << '\n';
cout << "(3, 1) " << test_all_string(3, 1) << '\n';
cout << "(4, 2) " << test_all_string(4, 2) << '\n';
cout << "(5, 2) " << test_all_string(5, 2) << '\n';
cout << dp_cont_2(5, 2);
return 0;
}
Here is a dp solution and a brute force solution. You can improve the DP solution by talking out the total array and reducing the other matrices to a pair of vectors that you swap on every cycle.
#include <iostream>
#include <vector>
using namespace std;
#include <stdint.h>
int count(char *s)
{
int c = 0;
int state = 0;
int i = 0;
while(s[i] != 0)
{
switch (state)
{
case 0: // last letter was con
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
state = 1;
}
break;
case 1: // last was vowle
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
if (s[i - 1] == s[i])
{
c++;
state = 2;
}
}
else
{
state = 0;
}
break;
case 2: // in a sequence
if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
{
if (s[i - 1] != s[i])
{
state = 1;
}
}
else
{
state = 0;
}
break;
}
i++;
}
return c;
} //----------------------------------------------------------------------------------------------------------------
int test_all_string_r(int n, int k, char *s, int l)
{
if (l == n)
{
//cout << s;
int x = count(s);
if (x == k)
{
//cout << " *\n";
return 1;
}
else
{
//cout << "\n";
return 0;
}
}
int sum = 0;
for (char c = 'A'; c <= 'Z'; c++)
{
s[l] = c;
sum = sum + test_all_string_r(n, k, s, l + 1);
}
return sum;
}//----------------------------------------------------------------------------------------------------------------
int test_all_string(int n, int k)
{
char *s = new char[n + 1];
s[n] = 0;
int out = test_all_string_r(n, k, s, 0);
delete[] s;
return out;
}//----------------------------------------------------------------------------------------------------------------
void dump(const vector<vector<uint64_t>> &in)
{
for (int y = 0; y < in[0].size(); y++)
{
for (int x = 0; x < in.size(); x++)
{
cout << in[x][y] << " ";
}
cout << "\n";
}
}
uint64_t dp_cont_2(int n, int k) // n > 1 and k > 0
{
vector<vector<uint64_t>> end_consonant(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_vowel_set(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> end_single_vowel(n + 1, vector<uint64_t>(k + 1, 0));
vector<vector<uint64_t>> total(n + 1, vector<uint64_t>(k + 1, 0));
end_consonant[1][0] = 26 - 5; // any of the consonants
end_single_vowel[1][0] = 5; // any of the vowels
total[1][0] = 26;
for (int ni = 2; ni <= n; ni++)
{
for (int ki = 0; ki <= k; ki++)
{
end_consonant[ni][ki] = total[ni - 1][ki] * (26 - 5); // ways of doing it with one less letter and then we add a new consonant at the end
uint64_t ec = end_consonant[ni][ki];
end_single_vowel[ni][ki] = end_single_vowel[ni - 1][ki] * 4 + // add a different vowel
end_vowel_set[ni - 1][ki] * 4 + // add a different vowel
end_consonant[ni - 1][ki] * 5; // add any vowel
uint64_t esv = end_single_vowel[ni][ki];
if (ki > 0)
{
uint64_t d = end_single_vowel[ni - 1][ki - 1];
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki] + d;
}
else
{
end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki];
}
end_vowel_set[ni][ki] = ((ki > 0) ? end_single_vowel[ni - 1][ki - 1] : 0) + // k went up so we need to have i-1
end_vowel_set[ni - 1][ki]; // add a vowel after eithe a uneque v and a set of vs
uint64_t evs = end_vowel_set[ni][ki];
total[ni][ki] = end_consonant[ni][ki] + end_vowel_set[ni][ki] + end_single_vowel[ni][ki]; // total ways with one less letter
uint64_t t = total[ni][ki];
}
}
cout << "--------end_consonant---------------------------------------\n";
dump(end_consonant);
cout << "--------end_vowel_set---------------------------------------\n";
dump(end_vowel_set);
cout << "--------end_single_vowel---------------------------------------\n";
dump(end_single_vowel);
cout << "--------total---------------------------------------\n";
dump(total);
cout << "-----------------------------------------------\n";
return total[n][k];
}
int _tmain(int argc, _TCHAR* argv[])
{
cout << "(1, 0) " << test_all_string(1, 0) << '\n';
cout << "(1, 1) " << test_all_string(1, 1) << '\n';
cout << "(2, 0) " << test_all_string(2, 0) << '\n';
cout << "(2, 1) " << test_all_string(2, 1) << '\n';
cout << "(3, 1) " << test_all_string(3, 1) << '\n';
cout << "(4, 2) " << test_all_string(4, 2) << '\n';
cout << "(5, 2) " << test_all_string(5, 2) << '\n';
cout << dp_cont_2(5, 2);
return 0;
}
In case the input includes number of distinct vowels:
- Alex October 24, 2017