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

- anoophky September 07, 2019 | Flag Reply
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])

- adr September 07, 2019 | Flag Reply
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

- ofir September 10, 2019 | Flag Reply
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)));
                }
            }
            
            Console.WriteLine(answer);
        }

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

- quangsangsem@gmail.com September 11, 2019 | Flag Reply
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);

return totalCombinations

- p__mann September 17, 2019 | Flag Reply
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);
return totalCombinations;

- p__mann September 18, 2019 | Flag Reply
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);
return totalCombinations;

- p__mann September 18, 2019 | 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