Facebook Interview Question
Developer Program EngineersCountry: United States
Interview Type: Written Test
for i in range(46):
if possibleMcNuggets[i]:
if i + 6 < 46: possibleMcNuggets[i + 6] = True
if i + 9 < 46: possibleMcNuggets[i + 9] = True
if i + 20 < 46: possibleMcNuggets[i + 20] = True
can be optimzed to do it recursively removing iteration where possibleMcnuggets[i] is false. this is bounded by 46, so can be done in preprocessing stage for more faster execution time.
hey, i understood your logic to check for number beyond 46..... but how did you come up with the number 46?
public class McNuggets {
public static boolean canBuyNMcNuggets(int n) {
return n >= 0 && (n == 0 || n % 6 == 0 || n % 9 == 0 || n % 20 == 0 || canBuyNMcNuggets(n - 6) || canBuyNMcNuggets(n - 9) || canBuyNMcNuggets(n - 20));
}
}
def McNuggets(n):
ret = False
if (n < 1):
return False;
if ((n % 6 == 0)or(n % 9 == 0)or(n % 20 == 0)):
return True
if (ret == False and n > 20):
ret = McNuggets(n - 20)
if (ret == False and n > 9):
ret = McNuggets(n - 9)
if (ret == False and n > 6):
ret = McNuggets(n - 6)
return ret
Dude...
This works well in Python, just arrange the indentation and it will be ok. The grader outputted correct
It will take 3^N time which is bad. You can use dynamic programming instead.
This recurrence relation could be used
P(m): True or False for is it possible to get m McNuggets.
P(m) = P(m-6) | P(m-9) | P(m-20).
P(n) would contain the final output.
O(n) time complexity and O(n) space complexity!
Time complexity with recursion is exponential. With DP it's not linear but pseudo-polynomial.
boolean McNuggets(int n)
{
boolean ret = false;
if (n < 1)
return false;
if ((n % 6 == 0) ||
(n % 9 == 0) ||
(n % 20 == 0))
return true;
if (ret == false && n > 20)
ret = McNuggets(n - 20);
if (ret == false && n > 9)
ret = McNuggets(n - 9);
if (ret == false && n > 6)
ret = McNuggets(n - 6);
return ret;
}
@Vinod: Why are you posting without running some test cases on your code. Your code fails for even basic cases leave trickier cases aside.
Check your code with n = 33 (20*0 + 9*3 + 6*1)
@nitingupta180: Have you tested his code?I bet you haven't.Please check that it works for 33 as well.
nitingupta180:Sorry my bad butit still works.
"@nitingupta180: Are you serious?I double checked for your amusement but this works well.
Just call mcNuggets(33) and check what it returns.
If I trust my machine it returns 1 which I think is right answer."
@anish: Ok lets walk through the code.
Call McNuggets(33)
Then it will substract 20 from it.
Call McNuggets(13)
Then it will substract 9 from it.
Call McNuggets(4)
Then it will return false.
nitingupta180: nope.That is now how it works.
33 in-turn will get checked with 9, 6
So 33-9 = 24 and (24%6 == 0) return true.
I would suggest you to solve recursion problems more to get good understanding.
@anish: I think you are wrong. How it will skip if condition which is checking for > 20 for the first time.
why not add some logs and check for yourself?It would really clarify your doubt.I strongly recommend you to not post any further on this and put some logs as below and check.
if (ret == false && n > 20)
ret = McNuggets(n - 20);
printf("n %d\n", n);
I just run the code and it is working for 33.
there after failed for:
Call McNuggets(33)
Then it will substract 20 from it.
Call McNuggets(13)
Then it will substract 9 from it.
Call McNuggets(4)
Then it will return false.
it will check 33-9 = 24 and (24%6 == 0) return true.
did u actually run the code?
@Anish, dude, you are confidently saying wrong :) For 33, your code should return after (33-20) check. So it will fail.
I think this problem is similar to Minimum Coin Problem. Given set of coin values. Find minimum no of coins required for a sum. This can be solved easily by dynamic programming.
Code goes like this.
int min(int n)
{
int packages[] = {1,9,20};
int size = sizeof(packages)/ sizeof(int);
int sum[n+1] = {INT_MAX};
for(int sum_counter = 1; sum_counter < n+1; sum_counter++)
{
for(int coin_counter = 0; coin_counter < size; coin_counter++)
{
if(packages[coin_counter] <= sum_counter &&
sum[sum_counter - packages[coin_counter]] < sum[sum_counter])
{
sum[sum_counter] = sum[sum_counter - packages[coin_counter]] + 1;
}
}
}
return sum[n];
}
The above code is is for Minimum Coin problem. We have to modify it to handle case where it is not possible and also I have replaced 6 by 1 so that index does not goes out of bound for above program.
Its 12 am. Feeling sleepy.
Just Give a thought to this approach.
Tell me if I am wrong.
# Fast analytical solution using modular arithmetic
def McNuggets(n):
c = -n % 3
n -= c*20
b = n // 3 % 2
n -= b*9
a = n // 6
return a >= 0
# Degenerate solution, since all large numbers are reachable
def McNuggets(n):
return n not in frozenset((1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43))
c = -n % 3
n -= c*20
b = n // 3 % 2
n -= b*9
a = n // 6
return a >= 0
Can you explain how that works? I'm appalled!
Sure, don't put this version into production. :)
Both 6 and 9 are divisible by 3. If n is not divisible by 3, then you can't sum to n with any number of just 6's or 9's. You'll need at least 1 or 2 of the 20-count packages. The first line figures out the minimum number of 20-count packages that will be necessary, so that the remaining sum is divisible by 3. In the second line, the n variable is decreased by the number of McNuggets in the 20-count packages.
At that point we know that the value in n is divisible by 3, (because we carefully chose the number of 20-count packages with just that goal in mind). Sometimes that number may not be divisible by 6 though. In that case, we need a minimum of 1 9-count package. So in the third line, we decide whether we need a 9-count package in order to make the remainder evenly divisible by 6. We'll need 0 or 1 9-count packages, but we'll never need more than 1 to make the remaining sum divisible by 6. In the fourth line, we decrease n by the number of McNuggets in the 9-count package, if there is one.
After that, whatever remains in n is divisible by 6, so we can divide to see how many 6-count packages would be needed.
The calculations above will work for any n, and will quickly find the minimum number of 20- and 9-count packages that are needed to arrive at the correct total. However, suppose that n is less than 40, and yet we calculate that we need a minimum of 2 20-count packages to get an exact sum. Those are the cases where it would be impossible to buy to n exactly. For example, if n is 19, then c will be 2 and b will be 1, and a will end up being -5. We would have to buy a minimum of 49 McNuggets just to turn n into something divisible by 6, but that is more than our original target of 19. The algorithm tries to compensate by buying a negative number of 6-count packages. That's why the final line tests to see if a is negative, because that means it is impossible to buy to that count exactly.
A lot of people try dynamic computing on this problem, because it looks similar to the "subset sum" problem, which is NP-complete. But there is a huge difference here: none of the package sizes are negative. That means that an analytic solution is possible. The first version I wrote runs in O(n) time, and the second in O(1) time.
Not all large numbers are reachable so the "Degenerate solution" is incorrect. Examples: 3422, 3428, 3431 and so on.
@nitingupta180: Are you serious?I double checked for your amusement but this works well.
Just call mcNuggets(33) and check what it returns.
If I trust my machine it returns 1 which I think is right answer.
def McNuggets(n):
"""
n is an int
Returns True if some integer combination of 6, 9 and 20 equals n
Otherwise returns False.
"""
# Your Code Here
ret = False
if (n < 1):
return False;
if ((n % 6 == 0)or(n % 9 == 0)or(n % 20 == 0)):
return True
if (ret == False and n > 20):
ret = McNuggets(n - 20)
if (ret == False and n > 9):
ret = McNuggets(n - 9)
if (ret == False and n > 6):
ret = McNuggets(n - 6)
return ret
#include<iostream>
using namespace std;
bool possible(int sum, int a1, int a2, int a3){
if(sum == 0){
cout<<a1<<" "<<a2<<" "<<a3;
return true;
}
if(sum <6) return false;
return possible(sum - 20, a1, a2, a3+1) || possible(sum - 9, a1, a2+1, a3) || possible(sum - 6, a1+1, a2, a3);
}
int main(){
int sum;
cin>>sum;
possible(sum, 0, 0, 0);
return 0;
}
## A solution for McNuggets problem on careercup (question?id=14974673)
##
##
validPacks = [20, 9, 6]
howmany = [0, 0, 0]
def McNuggets(n) :
""" Returns true or false, depending upon whether McNuggets for given
amount are possible. Additionally also gives the combination
"""
global howmany
for i in range(len(validPacks)):
curpack = validPacks[i]
if (n - curpack) >= 0:
retval = McNuggets(n-curpack)
howmany[i] += 1
if retval is True:
return retval
else:
howmany[i] -= 1
if n == 0:
return True
howmany = [0, 0, 0]
return False
for i in range(6,100):
howmany = [0, 0, 0]
print i, ":", McNuggets(i), howmany
This can be solved by breaking down the problem to its sub problems. Given a number, take 6 out of it. Can the rest be be broken up between {9, 20}? (and recurse). If not possible, then take 2*6 out of the number. Can the rest be broken up between {9, 20}? and so on.
Here is the code.
bool nuggets (int n)
{
vector<int> denoms;
denoms.push_back(6);
denoms.push_back(9);
denoms.push_back(20);
return isComboPossible(n, denoms);
}
bool isComboPossible (int n, vector<int> denoms)
{
bool bPossible = false;
int i;
if (n <= 0) {
return false;
}
for (i = 0; i < denoms.size(); ++i) {
int nHowMany = n / denoms[i];
bPossible = (n % denoms[i] == 0);
if (bPossible) {
cout << denoms[i] << " nuggets: " << nHowMany << endl;
return true;
}
}
if (denoms.size() == 1) {
return false;
}
int denom1 = denoms[0];
denoms.erase(denoms.begin());
for (i = 0; denom1 * i < n && !bPossible; ++i) {
bPossible = isComboPossible (n - denom1 * i, denoms);
}
if (bPossible) {
cout << denom1 << " nuggets: " << i - 1 << endl;
}
return bPossible;
}
Like someone mentioned below, its a coin change problem.
Code:
#include <iostream>
using namespace std;
int mcNuggets(int keys[], int key_size, int n)
{
if(key_size == 0)
return 0;
if(n == 0)
return 1;
int store[n+1];
for(int i = 1; i< n+1; i++)
store[i] = 0;
store[0] = 1;
for(int i = 0; i<key_size; i++)
for(int j = 0 ; j < n+1; j++) {
if(j >= keys[i])
store[j] = store[j] | store[j-keys[i]];
}
if(store[n] == 1)
return 1;
return 0;
}
int main(int argc, char **argv)
{
int keys[] = { 6, 9, 20};
int n;
cin >> n;
if(mcNuggets(keys, 3, n))
cout << "Possible" <<endl;
else
cout << "Not Possible" << endl;
}
#include<iostream>
#include<stdlib.h>
using namespace std;
int count(int *arr,int n,int number)
{
if(number==0) return 1;
if(number<0) return 0;
if(n<=0 && number>=1) return 0;
return count(arr,n,number-arr[n-1])+count(arr,n-1,number);
}
int main()
{
int arr[] = {6,9,20};
int m = sizeof(arr)/sizeof(arr[0]);
cout<< count(arr, m, 40);
return 0;
}
Eh, a brute force solution.
# desired_num: desired number of mcnuggets
def get_mcnuggets(desired_num):
current_num = 0
a, b, c = [0, 0, 0]
while 20*c <= desired_num:
b = 0
while 9*b <= desired_num:
a = 0
while 6*a <= desired_num:
current_num = 6*a + 9*b + 20*c
if current_num == desired_num:
return True
a += 1
b += 1
c += 1
return False
No one seems to have suggested the bottom-up approach of constructing a list of possible numbers until we either reach or exceed n. The list is {0} initially and gradually grows, such as {0, 6, 9, 12, 18, 20, 24, 27...}. In each iteration, we use 3 different indices to keep track of the numbers in the list to which we should add 6, 9 and 20 to. We then add their minimum to the list, and increment the relevant indices. We need to make sure we don't add numbers that are already in the list by checking that this minimum is actually greater than the maximum of the list.
static boolean possible2(int n) {
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(0);
int p6 = 0;
int p9 = 0;
int p20 = 0;
// compiler complains if we use while(true) here
for(int i=0; i<n; i++) {
int a = numbers.get(p6) + 6;
int b = numbers.get(p9) + 9;
int c = numbers.get(p20) + 20;
int min = min3(a, b, c);
if(min == n)
return true;
if(min > n)
return false;
if(min > numbers.get(numbers.size()-1))
numbers.add(min);
if(a == min)
p6++;
if(b == min)
p9++;
if(c == min)
p20++;
}
return false;
}
static int min3(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
What about:
bool mcNugget(int n)
{
static std::vector<int> notWorking = {1,2,3,4,5,7,8,10,11,13,14,16,17,10,22,23,25,28,31,34,37,43};
return notWorking.find(n) == notWorking.end();
}
LOL, seems as if all number above 43 can be composed by nuggets. So buy a lot and you can't be wrong... I verified it up to 2048 with brute force.
For the concrete case, use a little number theory in advance of coding:
6-packs + 9-packs only -> 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, etc.
add a 20-pack -> 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, etc...
add two 20-packs -> 40, 46, 49, 52, 55, 58, etc.
Basically, if you want more than 60 nuggets, you can always get your exact nugget meal.
For values less than 60, just hard code a lookup table or use the recursive algorithm, which is efficient enough for small numbers despite exponential time.
The only unreachable numbers are 1,2,3,4,5,7,8,10,11,13,14,16,17,19, 22, 23, 25, 28, 31, 34, 37, and 43.
This problem is the same as the ol' "minimum many quarters, dimes, nickels, and pennies do you need to make up x cents?" only quite a bit easier, because you don't need to keep track of a, b, c: you just need to determine if a, b, and c can exist such that their combination satisfies the conditional statement (6a + 9b + 20c == n)
And here it is in Python
def mcnuggets(n):
d = n
while d >= 20:
d = d - 20
while d >= 9:
d = d-9
while d >= 6:
d = d - 6
return d == 0
print mcnuggets(16)
It's also important to note that you can get it by taking the modulo of subsequently decreasing parts, as another answer here indicates (- Y):
return ( ( ( n % 20 ) % 9 ) % 6 == 0 )
But keep in mind that the code above is exactly what the hardware does in this case. It subtracts 20 until the number is below 20, then subtracts 9 from that number until that number is below 9, and then subtracts six from that number until that number is below 6. If the remaining number is 0, return True.
Not really important overall, but being able to mention both in an interview would definitely give you some nerd points xD
O(1) time complexity
bool integerDivide(int x,int &a,int &b,int &c)
{// 6a + 9b + 20c = x
// 0<= a < 9
// 0<= b < 20
// 0<= c
//==> 6*8 + 9*19 + 20c >= x
// ==> c>=(x-6*8-9*19)/20 && c>=0 && c <= x/20
if (x<0)
{
return false;
}
for (c=max((x - 6*8 -9*19)/20,0);c <= x/20;c++)
{//implement (6*8+19*9 )/ 20 times at most
int left_x = x - 20 * c;
for (a=0;a<9;a++)
{
for (b=0;b<20;b++)
{
if(left_x == 6*a + 9*b)
return true;
}
}
}
return false;
}
Two variations that run in O(1):
def McNuggets(n):
n %= 20
n %= 9
n %= 6
return n == 0
and
def McNuggets(n):
n %= 20
n %= 9
return n % 6 == 0
/**
*
* @author just_do_it
*
* Check if there exists positive integral solution to
* 6a + 9b + 20c = n
*
* you can assume n < 60
since for n>60, one of n-60, n-20 or n-40 is divisible by 3 and can be assembled from 6 and 9
*/
public class McDonaldPurchaseProblem {
/*static boolean solvable[] = new boolean[60];
static void precomputeSolvableNumbersLessThan60(){
}*/
static boolean solvable(int n){
if(n>=60) return true;
int m = n%60;
if(m == 0){
return true;
} else {
if(m %3 == 0){
if(m >=6){
return true;
}
} else if (m < 20){
return false;
}
if(m %20 == 0){
return true;
} else {
if(m>20 && (m-20) %3 == 0 && m-20 >= 6){
return true;
}
if(m>40 && (m-40) %3 == 0 && m-40 >= 6){
return true;
}
}
}
return false;
}
public static void main(String[] args){
for(int i = 1; i < 60; i++){
System.out.println(i + "\t" + solvable(i));
}
}
}
This doesn't work for me --- any suggestions --- please see the python code below:
def is_nugget_number(num):
for i in range(10):
for j in range(10):
for k in range(10):
if(i==0 and j==0 and k==0):
continue
if (num%(i*6 + j*9 + k*20)==0):
return True
return False
def main():
nuggets=1
canbuy=0
cantbuy=0
while(canbuy-cantbuy<6):
if (is_nugget_number(nuggets)):
canbuy = nuggets
print("canbuy: " + str(canbuy))
else:
cantbuy = nuggets
nuggets+=1
print("The highest number one can't buy =" + str(cantbuy))
My solution is to recursively calculate the combinations and return true when you find a solution, false if you are exhaustive.
static bool canbuyChickenNugget(int n)
{
//6a+9b+20c=n
if (n < 0) return false;
if (n == 0) return true;
if (canbuyChickenNugget(n - 6)) return true;
if (canbuyChickenNugget(n - 9)) return true;
if (canbuyChickenNugget(n - 20)) return true;
return false;
}
My solution is to recursively calculate the combinations and return true when you find a solution, false if you are exhaustive.
static bool canbuyChickenNugget(int n)
{
//6a+9b+20c=n
if (n < 0) return false;
if (n == 0) return true;
if (canbuyChickenNugget(n - 6)) return true;
if (canbuyChickenNugget(n - 9)) return true;
if (canbuyChickenNugget(n - 20)) return true;
return false;
}
Here you have a Python implementation of the solution using DP. As a lot of people said, this is very similar to the Coin Change Problem
PACKAGES = [6,9,20]
def mc_nuggets(packages, n):
# partial_solutions[i] is True if exists a possible combination of packages for i
partial_solutions = [True]
for i in range(1, n + 1):
partial_solutions.append(any([partial_solutions[i - p] if (i - p) >= 0 else False for p in packages]))
#print "Partial:", list(enumerate(partial_solutions))
return partial_solutions[n]
assert mc_nuggets(PACKAGES,1) == False
assert mc_nuggets(PACKAGES,5) == False
assert mc_nuggets(PACKAGES,6) == True
assert mc_nuggets(PACKAGES,9) == True
assert mc_nuggets(PACKAGES,12) == True
assert mc_nuggets(PACKAGES,10) == False
assert mc_nuggets(PACKAGES,16) == False
assert mc_nuggets(PACKAGES,20) == True
assert mc_nuggets(PACKAGES,29) == True
assert mc_nuggets(PACKAGES,26) == True
assert mc_nuggets(PACKAGES,27) == True
Here's my solution, not sure I'd come up with it under pressure. The hard part was coming up with the list of factors:
6
9
20
15
26
29
35
Not sure it's all that efficient either. The positive thing is that it uses a generator, so the value is yielded, though it's only 7 values.
from itertools import chain, combinations
from functools import reduce
def McNuggets(n):
sizes = [6,9,20] # portion sizes. Any combination of these factored will give you a valid portion size.
g = (subset for subset in chain(*map(lambda x: combinations(sizes, x), range(1, len(sizes)+1))))
for i in g:
f = reduce(lambda x,y: x + y , i)
if n%f == 0:
return True
return False
bool Check(int n)
{
n = n%20;
return n == 0 || n == 6 || n ==9 || n == 12 || n == 18;
}
The following is my O(1) time complexity, O(1) space complexity implementation in python 3:
Obviously, for any n larger than or equal to 46, the answer must be True.
- Alva0930 June 22, 2013(1) With zero package of 20, it is possible to buy 3x McNuggets where x is an integer larger than or equal to 2
(2) With one package of 20, it is possible to buy 3x + 2 McNuggets where x is an integer larger than or equal to 8
(3) With two packages of 20, it is possible to buy 3x + 1 McNuggets where x is an integer larger than or equal to 15