Google Interview Question for Software Engineers


Country: India
Interview Type: Phone Interview




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

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.

- Anonymous October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

In case the input includes number of distinct vowels:

uint64_t Count(int16_t n, int16_t k, int vowels_count, unordered_map<uint64_t, uint64_t> &memo, int prev_vowel = -1) {
	if (k < 0 ||
		n < 0)
	{
		return 0;
	}
	if (k == 0 &&
	    n == 0)
	{
		return 1;
	}

	uint64_t memo_key = ((uint64_t)n << 48) | ((uint64_t)k << 32) | prev_vowel;
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	uint64_t count = Count(n - 1, k, vowels_count, memo, -1);
	for (int vowel = 0; vowel < vowels_count; ++vowel) {
		count += Count(n - 1, prev_vowel == vowel ? k - 1 : k, vowels_count, memo, vowel);
	}

	memo[memo_key] = count;
	return memo[memo_key];
}

- Alex October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

But when K=0, you could still have N strings which do not have any consecutive vowels. Returning 1 is not correct for this case. This stumped me in my interview.
What does n<<48 and k<<32 do?

- anonymous October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@anonymous. That's right. Thank you! Fixed. It's "k == 0 && n == 0" instead of just "k == 0".

- Alex October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Regarding "n<<48 and k<<32". It's constructing the memo key so, that the values of n and k don't overlap.

- Alex October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex how would you call this?
also this
uint64_t count = prev_is_vowel
? Count(n - 1, k - 1, memo, true)
: Count(n - 1, k, memo, true);

should it not be
uint64_t count = prev_is_vowel
? Count(n - 1, k - 1, memo, true)
: Count(n - 1, k, memo, false);

- anonymous October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Alex October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex: for n = 3, k = 2: "AAA", "EEE", "III", "OOO", "UUU" = 5
I don't see how your code comes to this result (if it does, I read out, it returns 1). What did I miss?

- Chris October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. The input is only n and k. We don't have particular vowels. For n = 3, and k = 2, it's only one combination having foo == 2: 'VowelVowelVowel'.

- Alex October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex: The question was: "Set of letters (‘A’, ‘E’, ‘I’, ‘O’, ‘U’) are called vowels. Other letters are called consonants." ...

- Chris October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. I got it like an introduction, to explain how foo is calculated. Then, there goes "You are given 2 inputs, N and K". It may be the case I got it wrong. I've just posted the variant for the case when we know how many vowels we have.

- Alex October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex, sure, you get N and K with the previously explained rules I would suppose. so vowel_count = 5 (constant)

- Chris October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. You are probably right. I removed the first version, and left number of vowels variable to be compatible with different languages :)
O(n * k * v^2) time, O(n * k * v) space. Where v is number of vowels.

- Alex October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

go over all the 26^n strings and count

- littlefinger October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

f(n,k,is_previous_vowel)= {if yes then 21*f(n-1,k,false)+4*f(n-1,k,true)+1*f(n-1,k-1,true), if no then 25*f(n-1,k,false)+f(n-1,k,true)}

- littlefinger October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sudip.innovates October 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kkr.ashish October 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Dr.Milota October 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python simple solution

def cons_vowel(s):
  vowel = ['A','E','I','O','U']
  counter = 0
  for i in range(len(s)-1):
    if s[i] in vowel:
      if s[i] == s[i+1]:
        counter += 1
  
  return counter

- shahvansh123 October 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

}

- Anonymous November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

}"

- chaitanya November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

}

- chaitanya November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

}

- chaitanya November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- chaitanya November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- chaitanya November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- DR A.D.M October 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Dr.Milota October 26, 2017 | Flag Reply


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