## Facebook Interview Question for Software Development Managers

Country: United States

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

geeksforgeeks count-strings-can-formed-using-b-c-given-constraints

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

``````def count_abc(n, nb, nc):
if n == 1:
return 1 + (1 if nb else 0) + (1 if nc else 0)

ret = count_abc(n-1, nb, nc)
if nb > 0:
c2 = count_abc(n-1, nb-1, nc)
ret += c2
if nc > 0:
c3 = count_abc(n-1, nb, nc-1)
ret += c3
return ret

if __name__ == '__main__':
print(count_abc(1, 1, 2))
print(count_abc(2, 1, 2))
print(count_abc(3, 1, 2))
print(count_abc(4, 1, 2))
print(count_abc(5, 1, 2))
print(count_abc(6, 1, 2))
print(count_abc(7, 1, 2))
print(count_abc(100, 1, 2))``````

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

```
#include <iostream>
using namespace std;

int helper(int n, int nb, int nc) {
if (n == 0)
return 1;
int result = helper(n-1, nb, nc);
if (nb > 0)
result += helper(n-1, nb-1, nc);
if (nc > 0)
result += helper(n-1, nb, nc-1);
return result;
}

int main () {
int n = 5;
int nb = 1;
int nc = 2;
cout << "Number of possible strings: " << helper(n, nb, nc) << "\n";
return 0;
}
```

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

1) helper(1,1,2) should give 0!!!

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

I think this is a mathematical problem, what we need to do is to calculate all the number of possibilities, remove from it the occurrences of the not allowed doubles and triples.

Here is a simple Javascript code that may fix the problem.

The complexity of it is O(1)

Test cases were covered, n=1, n=2, n=3, n=4

n=1 => the output is 3
n=2 => the output is 8
n=3 => the output is 19
n=4 => the output is 39

``````let n = 4;
const buildingBlocksArray = ['a', 'b', 'c'];

let countTheNumberOfStrings = (wordsLength, buildingBlocksLength) => {

if(wordsLength === 1){
return buildingBlocksLength;
}

let getCountOfAllPoss = (wordsLength) => {
const countOfAll = Math.pow(buildingBlocksLength, wordsLength);
return countOfAll;
}

let countOfAll = getCountOfAllPoss(wordsLength);

let countOfDoubles = getCountOfAllPoss(wordsLength - 1) * (wordsLength - 1);
let countOfTriples = getCountOfAllPoss(wordsLength - 2) * (wordsLength - 2);

let notAllowedDoubles = countOfDoubles / 3;
let allowedTriples = countOfTriples / 3;

console.log('countOfAll =', countOfAll);
console.log('countOfDoubles =', countOfDoubles);
console.log('countOfTriples =', countOfTriples);
console.log('notAllowedDoubles =', notAllowedDoubles);
console.log('allowedTriples =', allowedTriples);

let finalResults = (countOfAll - notAllowedDoubles - countOfTriples) + allowedTriples;

if(wordsLength <= buildingBlocksLength){
return finalResults;
} else {
return finalResults - (buildingBlocksLength * (wordsLength - buildingBlocksLength))
}
}

console.log('finalResults =', countTheNumberOfStrings(n, buildingBlocksArray.length));``````

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

A straightforward DP problem

``````N = 10
dp = [[[1] * (N+1) for _ in [0,1]] for _ in [0,1,2]]
for l in range(1,N+1):
dp[2][1][l] = dp[2][1][l-1] + dp[2][0][l-1] + dp[1][1][l-1]
dp[1][1][l] = dp[1][1][l-1] + dp[1][0][l-1] + dp[0][1][l-1]
dp[0][1][l] = dp[0][1][l-1] + dp[0][0][l-1]
dp[2][0][l] = dp[2][0][l-1] + dp[1][0][l-1]
dp[1][0][l] = dp[1][0][l-1] + dp[0][0][l-1]

print (dp[2][1][N])``````

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

I think this can just be calculated (O(1)) (in code need to handle correctly cases of n < 3)
1+n+n+(n choose 2) + n*(n-1) + n*(n -1 choose 2)

1 - case of all As
n - case of all As and B
n - case of all As and C
(n choose 2) - case of all As and 2Cs
n*(n-1) - case of All As and B and C
n*(n -1 choose 2)- case of All As and B and 2 Cs

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

The problem is to output the total count of the strings that fit the criteria (length = n, bCount <= 1, cCount <=2)

Algorithm:
- Find all the possible combinations of aCount, bCount, cCount to form the string of length n;
Ex: n = 3 : aCount = 3, bCount = 0, cCount = 0; meaning there are 3 'a's, 0 'b' and 0 'c'in that string
aCount = 2, bCount = 1, cCount = 0;
aCount = 1, bCount = 1, cCount = 1;
.....
- Eliminate combinations that don't meet the criteria which is bCount <= 1 and cCount <= 2;
- For each combinations, calculate the number of distinct permutations
Ex: n = 4 : aCount = 2, bCount = 0, cCount = 2 ----> totalPermutations = n! / (aCount!*bCount!*cCount!) (This is a formulas for finding number of distict permutations)
In this case it would be 4!/(2!*0!*2!) = 6

Code:

``````public static int n = 4;
static void Main(string[] args)
{
string str = "";

int aCount = 0;
int bCount = 0;
int cCount = 0;

for (int a = 0; a <= n; a++)
{
aCount = a;
for (int b = 0; b <= n - aCount; b++)
{
bCount = b;
if (bCount > 1)
continue;
cCount = n - (aCount + bCount);
if (cCount > 2)
continue;
Console.WriteLine(aCount +" "+bCount+" "+cCount);
}
}

}

static int Factorial(int n)
{
int result = 1;
for (int i = 1; i <=n; i++)
{
result = result * i;
}

return result;
}``````

Output:
n = 1. Output: 3;
n = 2. Output: 8;
n = 3. Output: 19;
n = 4. Output: 39;
.
.
.

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

How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. {a,b,c}, and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. {-1,1,2}.
(Excuse my blend of code and pseudo-code)

int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)
int totalCombinations = 0;
if size of s == n then
return 1;
else
for each allowedLetter in allowedLetters keys:
create copy of allowedLettershashmap: tempAllowedLetters
lookup allowedLetter in tempAllowedLetters:
if value == 1 then
remove mapping from tempAllowedLetters
else
subtract 1 from value in mapping
totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);

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

How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. [a,b,c], and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. [-1,1,2].

int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)
int totalCombinations = 0;
if size of s == n then
totalCombinations = 1;
else
for each allowedLetter in allowedLetters keys:
create copy of allowedLetters: tempAllowedLetters
lookup allowedLetter in tempAllowedLetters:
if value == 1 then
remove mapping from tempAllowedLetters
else
subtract 1 from value in mapping
totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);

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

How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. {a,b,c}, and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. {-1,1,2}.

int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)
int totalCombinations = 0;
if size of s == n then
totalCombinations = 1;
else
for each allowedLetter in allowedLetters keys:
create copy of allowedLetters: tempAllowedLetters
lookup allowedLetter in tempAllowedLetters:
if value == 1 then
remove mapping from tempAllowedLetters
else
subtract 1 from value in mapping
totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);

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

``````function nStrings (n) {
var count = 0;
var possiblities = ['a', 'b', 'c'];
//                       /  |  \
//                      a    b   c
//                     /|\  /|\   \
//                     abc  abc     a
var recurse = function (stringSoFar, bs, cs) {
if(stringSoFar.length > n || bs > 1 || cs > 2) {
return;
} else if (stringSoFar.length === n) {
count ++;
return;
} else {
for(var i = 0; i < possiblities.length; i++) {
var b = 0;
var c = 0;
if(possiblities[i] === 'b') {
b = 1;
} else if (possiblities[i] === 'c') {
c = 1;
}

recurse(stringSoFar + possiblities[i], bs + b, cs + c);
}
}

};

recurse('', 0, 0);

return count;
}

// time O(n^n)
// space O(n^n)``````

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

``````#include <iostream>
using namespace std;

int helper(int n, int nb, int nc) {
if (n == 0)
return 1;
int result = helper(n-1, nb, nc);
if (nb > 0)
result += helper(n-1, nb-1, nc);
if (nc > 0)
result += helper(n-1, nb, nc-1);
return result;
}

int main () {
int n = 5;
int nb = 1;
int nc = 2;
cout << "Number of possible strings: " << helper(n, nb, nc) << "\n";
return 0;
}``````

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

here is the "generic solution". or at least, one version of it

``````static int big_o = 0;
static List<string> szOutStrings = new List<string>( );

static int helper( int n, int b, int [] LimitPerDigit, string szHeader )
{
// n == 0 === nothing. never gets here

// if we're the last digit (lenth 1), result is simply "are there still allowable #'s or not"
//
if ( n == 1 )
{
int resultZero = 0;
for ( int digit = 0 ; digit < b ; digit++ )
{
big_o++;
if ( LimitPerDigit [digit] > 0 )
{
resultZero++;
string szThis = ((char) ('a' + digit )).ToString( );
}
}
return resultZero;
}

// for each digit, if the digit is allowed, count up how many SUB-combinations are
// under that digit and add to total

int result = 0;

for ( int digit2 = 0 ; digit2 < b ; digit2++ )
{
if ( LimitPerDigit [digit2] > 0 )
{
// dock 1 for the limits per digit for this sub-inspection
LimitPerDigit [digit2]--;
string szThis = ((char) ('a' + digit2 )).ToString( );
result += helper( n - 1, b, LimitPerDigit, szHeader + szThis );
// then afterwards, bump it back up again
LimitPerDigit [digit2]++;
}
}

return result;
}

static void Main( string [] args )
{
int n = 10; // how many numbers
int b = 3; // what is the base
int [] LimitPerDigit = new int[b];
LimitPerDigit [1] = 1; // how many of each # can there be
LimitPerDigit [2] = 2;
LimitPerDigit [0] = n;

int result = helper( n, b, LimitPerDigit, "" );
Console.WriteLine( "total = " + result + ", big_o = " + big_o );

}``````

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

here's the solution showing each string as well

``````static int big_o = 0;
static List<string> szOutStrings = new List<string>( );

static int helper( int n, int b, int [] LimitPerDigit, string szHeader )
{
// n == 0 === nothing. never gets here

// if we're the last digit (lenth 1), result is simply "are there still allowable #'s or not"
//
if ( n == 1 )
{
int resultZero = 0;
for ( int digit = 0 ; digit < b ; digit++ )
{
big_o++;
if ( LimitPerDigit [digit] > 0 )
{
resultZero++;
string szThis = ((char) ('a' + digit )).ToString( );
}
}
return resultZero;
}

// for each digit, if the digit is allowed, count up how many SUB-combinations are
// under that digit and add to total

int result = 0;

for ( int digit2 = 0 ; digit2 < b ; digit2++ )
{
if ( LimitPerDigit [digit2] > 0 )
{
// dock 1 for the limits per digit for this sub-inspection
LimitPerDigit [digit2]--;
string szThis = ((char) ('a' + digit2 )).ToString( );
result += helper( n - 1, b, LimitPerDigit, szHeader + szThis );
// then afterwards, bump it back up again
LimitPerDigit [digit2]++;
}
}

return result;
}

static void Main( string [] args )
{
int n = 10; // how many numbers
int b = 3; // what is the base
int [] LimitPerDigit = new int[b];
LimitPerDigit [1] = 1; // how many of each # can there be
LimitPerDigit [2] = 2;
LimitPerDigit [0] = n;

int result = helper( n, b, LimitPerDigit, "" );
Console.WriteLine( "total = " + result + ", big_o = " + big_o );

}``````

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

``````int f(int l, int b, int c){

if(b<0 || c<0 || l<=0)
return 0;
if(l == 1){
if(b==0 && c==0)
return 1;
else if(b>0 && c >0)
return 3;
else
return 2;
}
else return f(l-1, b, c) + f(l-1, b-1, c) + f(l-1, b, c-1);
}

int main(){
cout<< f(n, 1, 2);
}``````

m = f(n, 1, 2)

1. first character is a
f(n-1, 1, 2)

2. first character is b
f(n-1, 0 2)
3. first character is c
f(n-1, 1, 1)

f(n, x, y) = f(n-1, x, y) + f(n-1, x-1, y) + f(n-1, x, y-1)

x=-1 or y=-1 -> f = 0

f(1, 0, 0) = 1
f(1, 1, 0) = 2
f(1, 0, 1) = 2
f(1, 0, 2) = 2
f(1, 1, 1) = 3
f(1, 1, 2) = 3

f(2, 1, 2) = f(1, 1, 2) + f(1, 0, 2) + f(1, 1, 1) = 3 + 2 + 3 = 8
f(2, 0, 2) = f(1, 0, 2) + f(1, -1, 2) + f(1, 1, 1) = 2 + 0 + 3 = 5
f(2, 1, 1) = f(1, 1, 1) + f(1, 0, 1) + f(1, 1, 0) = 3 + 2 + 2 = 7

f(3, 1, 2) = f(2, 1, 2) + f(2, 0, 2) + f(2, 1, 1) = 8 + 5 + 7 = 20

``````int f(int l, int b, int c){

if(b<0 || c<0 || l<=0)
return 0;
if(l == 1){
if(b==0 && c==0)
return 1;
else if(b>0 && c >0)
return 3;
else
return 2;
}
else return f(l-1, b, c) + f(l-1, b-1, c) + f(l-1, b, c-1);
}

int main(){
cout<< f(n, 1, 2);
}``````

m = f(n, 1, 2)

1. first character is a
f(n-1, 1, 2)

2. first character is b
f(n-1, 0 2)
3. first character is c
f(n-1, 1, 1)

f(n, x, y) = f(n-1, x, y) + f(n-1, x-1, y) + f(n-1, x, y-1)

x=-1 or y=-1 -> f = 0

f(1, 0, 0) = 1
f(1, 1, 0) = 2
f(1, 0, 1) = 2
f(1, 0, 2) = 2
f(1, 1, 1) = 3
f(1, 1, 2) = 3

f(2, 1, 2) = f(1, 1, 2) + f(1, 0, 2) + f(1, 1, 1) = 3 + 2 + 3 = 8
f(2, 0, 2) = f(1, 0, 2) + f(1, -1, 2) + f(1, 1, 1) = 2 + 0 + 3 = 5
f(2, 1, 1) = f(1, 1, 1) + f(1, 0, 1) + f(1, 1, 0) = 3 + 2 + 2 = 7

f(3, 1, 2) = f(2, 1, 2) + f(2, 0, 2) + f(2, 1, 1) = 8 + 5 + 7 = 20

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

There are C(n,3) ways of picking the b and c, and 3 ways of arranging them in that chosen place, so the answer is 3 * C(n,3).

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

``````## Given a length n, count the number of strings of length n that can be made
## using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

s1 = "abbccabaabbccabaabbccaba"
n = 5
s2 = "abcbabcbcbaacbcbbacbacbc"

def count_str(s, n):
if n > len(s):
return -1

count = 0
my_dict = dict.fromkeys(list('abc'), 0)

for ch in s[:n]:
my_dict[ch] += 1

for index in range(len(s) - (n - 1)):
if my_dict['b'] <= 1 and my_dict['c'] <= 2:
count += 1

my_dict[s[index]] -= 1
if index + n < len(s):
my_dict[s[index + n]] += 1

return count

print(count_str(s1, n)) # 5
print(count_str(s2, n)) # 3``````

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

``````## Given a length n, count the number of strings of length n that can be made
## using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

s1 = "abbccabaabbccabaabbccaba"
n = 5
s2 = "abcbabcbcbaacbcbbacbacbc"

def count_str(s, n):
if n > len(s):
return -1

count = 0
my_dict = dict.fromkeys(list('abc'), 0)

for ch in s[:n]:
my_dict[ch] += 1

for index in range(len(s) - (n - 1)):
if my_dict['b'] <= 1 and my_dict['c'] <= 2:
count += 1

my_dict[s[index]] -= 1
if index + n < len(s):
my_dict[s[index + n]] += 1

return count

print(count_str(s1, n)) # 5
print(count_str(s2, n)) # 3``````

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

geeksforgeeks count-strings-can-formed-using-b-c-given-constraints

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

does anyone know if this is legit? rooftopslushie.com/request/Facebook-EMEngineering-Manager-Onsite-Interview-109

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

``````public int count(int N){
return helper(N, aCount, bCount);
}

int helper(int N,int  cCount,int  bCount){
if(N==0) return 1;
if(bCount < 0 || cCount < 0) return0;
int res = helper(N-1, cCount, bCount);
res+= helper(N-1, cCount-1, bCount);
res+= helper(N-1, cCount, bCount-1)
return res;
}``````

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

``````class Solution {
public static void main(String[] args) {

int n = 6;

Map<String, Integer> alphabet = new HashMap<>();
alphabet.put("a", n);
alphabet.put("b", 1);
alphabet.put("c", 2);

List<String> allWords = new ArrayList<>();

for (String string : allWords) {
System.out.println(string);
}

System.out.println("The number of string is " + allWords.size());
}

private static void addLetter(int n, int ind, String prefix, Map<String, Integer> alphabet, List<String> allWords) {
if (ind == n) {
return;
}

for (String letter : alphabet.keySet()) {
if (alphabet.get(letter) > 0) {
alphabet.put(letter, alphabet.get(letter) - 1);
alphabet.put(letter, alphabet.get(letter) + 1);
}
}
}
}``````

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

This gives all the permutations. To get the number, add the following line.

``System.out.println("The number of string is " + allWords.size());``

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

``````import java.io.*;
import java.util.*;

/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/

class Solution {
public static void main(String[] args) {

List<String> res= genList(4);
System.out.println(res.size());
print(res);

}

public static void print(List<String> l){
for(String s: l){
System.out.println(s);
}
}

public static char[] chars= {'a','b','c'};

public static List<String> genList(int n){
List<String> res= new ArrayList<String>();
if(n<=0){
return res;
}
if(n>=1){
for(int j=0; j<chars.length; j++)
}

for(int i=1;i< n; i++){
String[] tArray= new String[res.size()];
res.toArray(tArray);
res.clear();

for(int k=0; k<tArray.length;k++){
String ts = tArray[k];
for(int j=0;j <3; j++){
String ns =ts+chars[j];
if(validateS(ns))
}
}
}

return res;
}

public static boolean validateS(String s){
char[] cs= s.toCharArray();
int numb=0, numc=0;
for(char c: cs){
if(c=='b'){
numb++;
}
if(c=='c'){
numc++;
}
}

if(numb <=1 && numc<=2){
return true;
}
return false;

}
}``````

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

A simple O(1) algorism:

``````public class FB1 {
public static void main(String[] argu) {
for (int i=1; i<5; i++) {
BigInteger result = solve(i);
System.out.println(i +", result is " + result);
}
}

private static BigInteger solve(int n) {
}

private static BigInteger choose(int n, int k) {
BigInteger r = BigInteger.ONE;
for (int i=0; i<k; i++) {
r = r.multiply(BigInteger.valueOf(n - i));
}
for (int i=2; i<=k; i++) {
r = r.divide(BigInteger.valueOf(i));
}

// System.out.println(n + "," + k + " = " + r);
return r;
}
}``````

output:

1, result is 3
2, result is 8
3, result is 19
4, result is 39

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

int max_abc(int nA, int nB, int nC)
{
if ((nB < 0) || (nC < 0))
return 0;
if (nA == 0)
return 1;
if ((nB == 0) && (nC == 0))
return 1;
int res = max_abc(nA-1, nB, nC);
res += max_abc(nA-1, nB-1, nC);
res += max_abc(nA-1, nB, nC-1);
return res;
}

int main()
{
int nA =3, nB = 1, nC =2;
printf("max %d \n", max_abc(nA, nB, nC));
return 0;
}

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

``````int max_abc(int nA, int nB, int nC)
{
if ((nB < 0) || (nC < 0))
return 0;
if (nA == 0)
return 1;
if ((nB == 0) && (nC == 0))
return 1;
int res = max_abc(nA-1, nB, nC);
res += max_abc(nA-1, nB-1, nC);
res += max_abc(nA-1, nB, nC-1);
return res;
}

int main()
{
int nA =3, nB = 1, nC =2;
printf("max %d \n", max_abc(nA, nB, nC));
return 0;
}``````

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

``````/*
Find the number of strings of length 'n' that could be formed with letters
'a', 'b' and 'c', given the constraint that the letter 'b' could only be used once
and the letter 'c' could only be used twice.
*/

#include <iostream>
#include <vector>

using namespace std;

void fooCore(vector<char>& vec, int currIndex, int maxIndex, int& count, int& bCount, int& cCount)
{
if (currIndex > maxIndex)
{
++count;
return;
}

// for 'a'
vec[currIndex] = 'a';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, cCount);

// for 'b'
if (bCount == 1)
{
vec[currIndex] = 'b';
fooCore(vec, currIndex + 1, maxIndex, count, --bCount, cCount);
++bCount;
}

// for 'c'
if (cCount == 1 || cCount == 2)
{
vec[currIndex] = 'c';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, --cCount);
++cCount;
}
}

int foo(int n)
{
if (n <= 0)
{
return 0;
}

vector<char> vec;
vec.resize(n);

int count{};
int bMaxCount = 1;
int cMaxCount = 2;

fooCore(vec, 0, n - 1, count, bMaxCount, cMaxCount);

return count;
}

int main()
{
cout << foo(0) << '\n';
cout << foo(1) << '\n';
cout << foo(2) << '\n';
cout << foo(3) << '\n';

return 0;
}

/*
0
3
8
19
*/``````

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

``````/*
Find the number of strings of length 'n' that could be formed with letters
'a', 'b' and 'c', given the constraint that the letter 'b' could only be used once
and the letter 'c' could only be used twice.
*/

#include <iostream>
#include <vector>

using namespace std;

void fooCore(vector<char>& vec, int currIndex, int maxIndex, int& count, int& bCount, int& cCount)
{
if (currIndex > maxIndex)
{
++count;
return;
}

// for 'a'
vec[currIndex] = 'a';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, cCount);

// for 'b'
if (bCount == 1)
{
vec[currIndex] = 'b';
fooCore(vec, currIndex + 1, maxIndex, count, --bCount, cCount);
++bCount;
}

// for 'c'
if (cCount == 1 || cCount == 2)
{
vec[currIndex] = 'c';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, --cCount);
++cCount;
}
}

int foo(int n)
{
if (n <= 0)
{
return 0;
}

vector<char> vec;
vec.resize(n);

int count{};
int bMaxCount = 1;
int cMaxCount = 2;

fooCore(vec, 0, n - 1, count, bMaxCount, cMaxCount);

return count;
}

int main()
{
cout << foo(0) << '\n';
cout << foo(1) << '\n';
cout << foo(2) << '\n';
cout << foo(3) << '\n';

return 0;
}

/*
0
3
8
19
*/``````

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

``````def count_abc(n, nb, nc):
if n == 1:
return 1 + (1 if nb else 0) + (1 if nc else 0)

ret = count_abc(n-1, nb, nc)
if nb > 0:
c2 = count_abc(n-1, nb-1, nc)
ret += c2
if nc > 0:
c3 = count_abc(n-1, nb, nc-1)
ret += c3
return ret

if __name__ == '__main__':
print(count_abc(1, 1, 2))
print(count_abc(2, 1, 2))
print(count_abc(3, 1, 2))
print(count_abc(4, 1, 2))
print(count_abc(5, 1, 2))
print(count_abc(6, 1, 2))
print(count_abc(7, 1, 2))
print(count_abc(100, 1, 2))``````

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

This is a typical dynamic programing question.

``````public static int countWordsDynamic(int n, int bCount, int cCount) {
int[][][] counts = new int[n + 1][bCount + 1][cCount + 1];
for (int i = 0; i <= bCount; i++) {
for (int j = 0; j <= cCount; j++) {
counts[0][i][j] = 1;
}
}

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= bCount; j++) {
for (int k = 0; k <= cCount; k++) {
counts[i][j][k] = counts[i - 1][j][k];
if (j > 0) {
counts[i][j][k] += counts[i - 1][j - 1][k];
}
if (k > 0) {
counts[i][j][k] += counts[i - 1][j][k - 1];
}
}
}
}
return counts[n][bCount][cCount];
}``````

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

You don't count the As, you count the Bs and the Cs.
0B-1C = n
1B-1C= n choose 2 = n(n-1)/2!
2B-1C = n choose 3 = n(n-1)(n-2)/3!
2B-0C = n choose 2 = n(n-1)/2!
1B-0C = n
0B -0C = 1
Sum = n(n-1) + 2n + 1 + n choose 3 = (6*n^2 + 6n + 6 + n^3 -3* n*2 + 2n) /6
= (n^3 + 3n^2 + 8n + 6)/6 = n(n-1)(n-2)/6 + n+1
This sum is an integer because n+1 is an integer and n(n-1)(n-2) is divisible by 3 and 2:-)

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

``````function countChar(str, char) {
let count = 0;
for (let i=0; i<str.length; i++) {
if (str[i] === char) {
count++;
}
}
return count;
}
function getStringsWithCharsInLengthN(n) {
let sum = 0;
let stringArr = [];
if (n >= 1) {
let newStringArr = ['a', 'b', 'c'];
for (let i = 1; i<n; i++) {
newStringArr.forEach((string)=> {
if (countChar(string, 'b') < 1) {
stringArr.push(string + 'b');
}
if (countChar(string, 'c') < 2) {
stringArr.push(string + 'c');
}
stringArr.push(string + 'a');
});
newStringArr = stringArr;
stringArr = [];
}
stringArr = newStringArr;
}
return stringArr.length;
}

console.log("Length for string with 1 character: " + getStringsWithCharsInLengthN(1));
console.log("Length for string with 2 characters: " + getStringsWithCharsInLengthN(2));
console.log("Length for string with 3 characters: " + getStringsWithCharsInLengthN(3));
console.log("Length for string with 4 characters: " + getStringsWithCharsInLengthN(4));
console.log("Length for string with 5 characters: " + getStringsWithCharsInLengthN(5));
console.log("Length for string with 6 characters: " + getStringsWithCharsInLengthN(6));``````

output:
Length for string with 1 character: 3
Length for string with 2 characters: 8
Length for string with 3 characters: 19
Length for string with 4 characters: 39
Length for string with 5 characters: 71
Length for string with 6 characters: 118

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

``````def findCounts(n, bcount, ccount):

if bcount < 0 or ccount < 0:
return 0
if n == 0: # no more chars left to be added
return 1

if bcount ==0  and ccount == 0:
return 1

res = findCounts(n-1,bcount, ccount) # if a is added

res += findCounts(n-1,bcount-1, ccount) # if b is added

res += findCounts(n-1, bcount, ccount-1) # if c is added

return res

print(findCounts(4,1,2))``````

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

if (0 == n || (0 == b && 0 == c)) {
return 1;
}

return solution(b, c, n-1) + (b > 0 ? solution(b-1, c, n-1) : 0) + (c > 0 ? solution (b, c-1, n-1) : 0);

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

{
if (0 == n || (0 == b && 0 == c)) {
return 1;
}

return solution(b, c, n-1) + (b > 0 ? solution(b-1, c, n-1) : 0) + (c > 0 ? solution (b, c-1, n-1) : 0);
}

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

public static int solution(int b, int c, int n) {

if (0 == n || (0 == b && 0 == c)) {
return 1;
}

return solution(b, c, n-1) + (b > 0 ? solution(b-1, c, n-1) : 0) + (c > 0 ? solution (b, c-1, n-1) : 0);
}

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

``````# Given a length n, count the number of strings of length n that can be made
# using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

def num_strings(n: int) -> int:
case_all_a = 1
case_c = n
case_b = n
case_cc = n * (n - 1) / 2  # divide by 2 since the order doesn't matter
case_cb = n * (n - 1)
case_ccb = n * (n - 1) * (n - 2) / 2

res = case_all_a
if n > 0:
res += case_c + case_b

if n > 1:
res += case_cc + case_cb

if n > 2:
res += case_ccb

return res

for i in range(5):
print(f"num_strings({i}) => {num_strings(i)}")``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Code:
#include <iostream>
using namespace std;

// To execute C++, please define "int main()"
int factorial(int n)
{
if (n==0)
return 1;
else
return n*factorial(n-1);
}
void count_c(int n)
{
int aCount=0;
int bCount=0;
int cCount=0;
int Sum=0;

for (aCount=0;aCount < n+1; aCount++)
{
for (bCount=0;bCount < 2; bCount++)
{
for (cCount=0;cCount < 3;cCount++)
{
if (aCount+bCount+cCount == n)
{
Sum=Sum+(factorial(n)/ (factorial(aCount) * factorial(bCount) *factorial(cCount)));

}
}
}

}

cout<<Sum<<endl;

}

int main() {

int n=5;
count_c(n);
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

{#include <iostream>
using namespace std;

// To execute C++, please define "int main()"
int factorial(int n)
{
if (n==0)
return 1;
else
return n*factorial(n-1);
}
void count_c(int n)
{
int aCount=0;
int bCount=0;
int cCount=0;
int Sum=0;

for (aCount=0;aCount < n+1; aCount++)
{
for (bCount=0;bCount < 2; bCount++)
{
for (cCount=0;cCount < 3;cCount++)
{
if (aCount+bCount+cCount == n)
{
Sum=Sum+(factorial(n)/ (factorial(aCount) * factorial(bCount) *factorial(cCount)));

}
}
}

}

cout<<Sum<<endl;

}

int main() {

int n=5;
count_c(n);
return 0;
}}

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

``````/*
Find the number of strings of length 'n' that could be formed with letters
'a', 'b' and 'c', given the constraint that the letter 'b' could only be used once
and the letter 'c' could only be used twice.
*/

#include <iostream>
#include <vector>

using namespace std;

void fooCore(vector<char>& vec, int currIndex, int maxIndex, int& count, int& bCount, int& cCount)
{
if (currIndex > maxIndex)
{
++count;
return;
}

// for 'a'
vec[currIndex] = 'a';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, cCount);

// for 'b'
if (bCount == 1)
{
vec[currIndex] = 'b';
fooCore(vec, currIndex + 1, maxIndex, count, --bCount, cCount);
++bCount;
}

// for 'c'
if (cCount == 1 || cCount == 2)
{
vec[currIndex] = 'c';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, --cCount);
++cCount;
}
}

int foo(int n)
{
if (n <= 0)
{
return 0;
}

vector<char> vec;
vec.resize(n);

int count{};
int bMaxCount = 1;
int cMaxCount = 2;

fooCore(vec, 0, n - 1, count, bMaxCount, cMaxCount);

return count;
}

int main()
{
cout << foo(0) << '\n';
cout << foo(1) << '\n';
cout << foo(2) << '\n';
cout << foo(3) << '\n';

return 0;
}

/*
0
3
8
19
*/``````

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.