Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
I start by thinking of it as a coin problem - given a total amount, how many different ways can you get that amount? So the 'score' is the amount, and the points are the coin values.
For example, if score was s=100, and points were either {3, 5, 7} the minimum number of shots scored would be 16 (7x13 + 3x3). You can work backwards from there to find all other possible combinations of shots that would result in a score of 100.
For each individual combination of shots, you then have to multiply by the different ways those shots could be ordered. For example, all thirteen 7 pointers followed by the three 3 pointers, etc.
This is calculated by [total shots]! / [score-count-1]![score-count-2]!... so, there are 16!/13!3! or 560 different ways you could make thirteen 7-pointers and three 3-pointers.
#define SIZE 3
int tab[SIZE]={4, 10, 15};
int score=80;
int f(s)
{
printf(" %d", s);
if(s<0)
{
printf(" nope\n");
return(0);
}
else
if(!s)
{
printf(" found\n");
return(1);
}
else
{
return(f(s-tab[0]) || f(s-tab[1]) || f(s-tab[2]));
}
}
The lines ending with found is the results
// example
// f(4)
//
// 1 1 1 1
// 2 1 1
// 1 2 1
// 1 1 2
// 2 2
// 3 1
// 1 3
// 4
public static void main(String[] args) {
assert getSeqCount(4) == 8;
assert getSeqCount2(4) == 8;
}
/**
* DP (quadratic)
*/
private static int getSeqCount2(int n) {
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i < dp.length; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j];
}
}
return dp[n];
}
/**
* naive recursive (exponential)
*/
private static int getSeqCount(int n) {
if (n <= 1) {
return 1;
}
int res = 0;
for (int i = 1; i <= n; i++) {
int newN = n - i;
if (newN >= 0) {
res += getSeqCount(newN);
}
}
return res;
}
bool is_bst(struct Node * node) {
return (node->left == NULL && node->right == NULL) ||
(
(node->left == NULL || (node->left->value<=node->value && is_bst(node->left)
&&
(node->right == NULL || (node->right->value>=node->value && is_bst(node->right);
);
}
What's a scoring sequence? I think I may know what kind of thing you're talking about. Is this problem akin to "If a basketball team scored 80 points in a game, how many scoring sequences of 2 or 3 points are possible?" In this case, the answer would be F(n) = F (n-2) + F(n-3), subject to base cases of F(2) = F(3) = 1 and F(1) = 0.
- eugene.yarovoi March 06, 2012