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.
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.
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 = [[ * (N+1) for _ in [0,1]] for _ in [0,1,2]]
for l in range(1,N+1):
dp[l] = dp[l-1] + dp[l-1] + dp[l-1]
dp[l] = dp[l-1] + dp[l-1] + dp[l-1]
dp[l] = dp[l-1] + dp[l-1]
dp[l] = dp[l-1] + dp[l-1]
dp[l] = dp[l-1] + dp[l-1]

print (dp[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
- Add them all up to get the answer

Code:

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

int aCount = 0;
int bCount = 0;
int cCount = 0;
int answer = 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);
answer = answer + (Factorial(n) / (Factorial(aCount) * Factorial(bCount) * Factorial(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; // how many of each # can there be
LimitPerDigit  = 2;
LimitPerDigit  = 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; // how many of each # can there be
LimitPerDigit  = 2;
LimitPerDigit  = 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.
-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;
}}

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.