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

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.