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

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

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?

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

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.

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

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

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?

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

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

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.

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)

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.

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

go over all the 26^n strings and count

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

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

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

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

}

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

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``````

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

}

}

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

}

}"

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

}``````

}

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

}

}``````

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

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

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

}

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

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

}

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

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.