Google Interview Question SDE1s
Country: India
Here is the c++ code, using DP.
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n; i++)
#define rep2(i,m,n) for(int i=m;i<(int)n; i++)
int PossibleDiceRolls(int S, int A, int N) {
vector< vector<int> > sum;
sum.resize(S+1);
rep(i,S+1)
sum[i].assign(N+1,0);
rep(i,min(A+1,S+1))
sum[i][1] = 1;
rep2(n,2,N+1)
rep2(i,1,S+1)
rep2(j,1,A+1)
if(i-j>0)
sum[i][n]+=sum[i-j][n-1];
return sum[S][N];
}
int main()
{
cout << PossibleDiceRolls(6, 6, 3) << endl;
return 0;
}
Same solution as described by Vinay:
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
int NoOfSol(int A, int N, int S, map<pair<int, int>, int>& m, vector<int>& vs)
{
if (S < 0) return 0;
if (N==1) {
if (S >= 1 && S<= A) {
for (int i=0; i<vs.size(); i++) {
cout << vs[i] << ", " ;
}
cout << S << endl;
return 1;
}
return 0;
}
if (m.count(make_pair(N,S)) != 0)
{
int cnt = m.at(make_pair(N,S));
if (cnt < 1) return cnt;
cout << "[";
for (int i=0; i<vs.size(); i++) {
cout << vs[i] << ", " ;
}
cout << " <sols> : "<< cnt << "]"<<endl;
return cnt;
}
int sol = 0;
for (int i=1; i<=A; i++) {
vs.push_back(i);
sol += NoOfSol(A, N-1, S-i, m, vs);
vs.pop_back();
}
m.insert(make_pair(make_pair(N,S), sol));
return sol;
}
int main(int argv, char** argc[])
{
int A = 6;
int N = 5;
int S = 10;
map<pair<int, int>, int> m;
vector<int> vs;
cout << "Solutions : " << NoOfSol(A, N, S, m, vs) << endl;
return 0;
}
I use JavaScript
function get_dice(s,n,a){
var method = 0;
if(n===1){
if(s>0&&s<=a)
return 1;
else
return 0;
}
for(var i =1;i<=a;i++){
method+=get_dice(s-i,n-1,a);
}
return method;
}
I am sorry but it seems like I got this question in different way and I could only get this in Polynomial time.
I mean using binomial theorem it get ( N is a variable number of Die and F is a variable number of faces of each die) so
N1(F)+N2(F)......N(n-1)(F)+N(n)(F)=S
Which clearly frames polynomial expression.
Any Pointers??
@lru_cache(maxsize = None)
def numOfWays(dices, max_dice_value, base_sum):
if base_sum == 0 or (dices == 1 and base_sum > max_dice_value):
return 0
if base_sum == dices or (dices == 1 and base_sum < max_dice_value):
return 1
total = 0
for val in range(1, min(max_dice_value, base_sum) + 1):
curWaysCount = numOfWays(dices-1, max_dice_value, base_sum - val)
total += curWaysCount
return total
@lru_cache(maxsize = None)
def numOfWays(dices, max_dice_value, base_sum):
if base_sum == 0:
return 0
if base_sum > max_dice_value * dices:
return 0
if base_sum == dices or (dices == 1 and base_sum < max_dice_value):
return 1
total = 0
for val in range(1, min(max_dice_value, base_sum) + 1):
if val > base_sum:
break
if (base_sum - val) == 0 and dices == 1:
total += 1
else:
total += numOfWays(dices-1, max_dice_value, base_sum - val)
return total
public static int sum(int[] atp) {
int sum = 0;
for (int i = 0; i < atp.length; ++i) {
sum += atp[i];
}
return sum;
}
public static void tryDice(final int[] atp, final int F, final int N, final int count, final int S) {
if (count > N - 1) {
int sum = sum(atp);
if(sum == S){
for (int i = 0; i < atp.length; i++) {
System.out.print(atp[i] + " ");
}
System.out.println();
}
return;
}
int cnt = count + 1;
for (int i = 1; i <= F; ++i) {
int[] newAtp = new int[atp.length];
System.arraycopy(atp, 0, newAtp, 0, atp.length);
newAtp[count] = i;
tryDice(newAtp, F, N, cnt, S);
}
}
public static void main(String args[]) {
int F = 3;
int D = 6;
int[] atp = new int[D];
int S = 10;
tryDice(atp, F, atp.length, 0, S);
}
public static void main(String[] args) {
for( int i = 2; i<= 12; i++){
System.out.println(i + " " + solutions(i,0,2, 6));
}
}
public static int solutions(int sum, int accum, int n, int A){
if( n == 0){
return 0;
}
int solutions = 0;
for( int i = 1; i<= A; i++){
int newAccum = accum +i;
if( n==1){
if( newAccum == sum){
solutions += 1;
break;
}
} else if( newAccum >= sum){
break;
} else {
solutions += solutions( sum, newAccum, n-1, A);
}
}
return solutions;
}
Here is a solution with DP and recursion. At each level of the recursion, fix the value of one dice.
UINT NumWays(UINT N, UINT A, UINT SUM)
{
INT_PAIR index;
static unordered_map<INT_PAIR, INT, Compare> lookup;
if (N==1)
{
if ( (SUM>0) && (A>= SUM))
{
return 1;
}
else
{
return 0;
}
}
index.first = N;
index.second = SUM;
unordered_map<INT_PAIR, INT>::iterator it;
it = lookup.find(index);
if (it != lookup.end())
{
return it->second;
}
UINT count = 0;
for (UINT i=1; i <=A; i++)
{
if (SUM >= i)
{
count += NumWays(N-1, A, SUM-i);
}
}
lookup[index]=count;
return count;
}
if this is just finding number of ways,then here is the answer :
1.This is equivalent to x1+x2+x3+...+xn=S where 1<=x1,x2,x3,..xn<=A where x1,x2,..xn are variables whose values are specified on each dice respectively
2.so now let t1=x1-1,t2=x2-1,t3=x3-1,...so now we have (x1-1)+(x2-1)+..+(xn-1)=S-(1+1+..1)=S-n
3.so now we have t1+t2+t3+..+tn=S-n where 0<=t1,t2,..tn<=A-1
4.The number of ways of forming x1+x2+..xr=n where x1,is (n+r-1)C(r-1)(there is a proof :))
5.so now the number of ways = (S-n+n-1)C(n-1)=(S-1)C(n-1) (where nCr=n!/(n-r)!(r!) )
You are right, except you don't account the fact that the xi <= A.
The formula (S-1)C(n-1) gives you the number of combinations to get the sum S from n values xi with 1 <= xi <= S-n+1. But unfortunately S-n+1 might be larger than A.
Example: S = 6, N = 3 and A = 3
Above formula leads to 5C2 = 5!/(3!*2!) = 10
explicitely these combinations:
1+1+4
1+2+3
1+3+2
1+4+1
2+1+3
2+2+2
2+3+1
3+1+2
3+2+1
4+1+1
but in fact we can't draw a 4 if A = 3. Thus the total number of combinatiosn is 7 and not 10.
A simple DP approach:
The function can be written as:
F(N, A, S) = F(N - 1, A, S - 1) + F(N - 1, A, S - 2) +........+ F(N - 1, A, S - A)
Where, The F(N, A, S) represents the number of ways of getting S with N dice each with A faces, numbered from 1 to A.
Explaining the above equation in words,
Find the number of ways of getting Sum (S - 1) from (N - 1) dice +
Find the number of ways of getting Sum (S - 2) from (N - 1) dice +
.................
..................
Find the number of ways of getting Sum (S - A) from (N - 1) dice
Carefully handle the base cases like:
1. N = 1, S > A
2. S < 1
a simple implementation is given below which can be memo-ed of course
int foo(int N, int A, int S){
if(N<=0)
return 0;
if(N==1){
if(S>=1 && S<=A)
return 1;
else
return 0;
}
int sol = 0;
for(int i=1; i<=A; ++i){
sol += foo(N-1, A, S-i);
}
return sol;
}
int main(){
int A = 6;
int N = 2;
int S = 10;
cout<<foo(N, A, S)<<endl;
return 1;
}
Feel free to correct my answer: the base case is where we roll one dice (N = 1). If number of faces (A) is greater than the sum (S), there is always one possible way.
Other cases: F(n, s, a) = Sum of F(n - 1, s - i, i) where i is 1 to number of faces (A).
def count(n, s, a):
if n < 0 or s < 0 or a < 0:
return 0
if n == 0 and s == 0:
return 1
if n == 1:
return a >= s ? 1 : 0
if n > s:
return 0
ret = 0
for i in xrange(1, a + 1):
ret += count(n - 1, s - i, i)
return ret
Correct me if I'm wrong, but the question does not ask how many permutations of the dice (BTW dice is plural for dice). The question simply asked how many ways the dice sum to S. There is only one way; the dice must add up to S.
One of these random objects is called a die. The plural is dice. "Dices" is not an English word and shows ignorance. It is difficult for me to believe that Google would make such obvious English errors in one of their questions.
Oh wait! I'm on an Indian site? How did I arrive here? How do we lose so many jobs to this counry if, not only can they not conjugate Engish correctly, they can't even figure out a simple probibliy/permutation problem? So sad for everybody.
@native english speaker: Morons like you is why the world hates America.
Now, go ahead, correct me, and say, "Morons like you _are_ why the word hates America".
@Anonymous: It is obvious that he (native english speaker #1) is a total idiot, given his answer of "just one way". Sad that such people don't even have the brains to realize how stupid they actually are. Being a racist on top of that, is just pitiable, and I just hope that he is just a benign one, restricted to making idiotic comments on the internet.
Guys correct me, if I am wrong. The question in non polynomial (NP) problem. Given N dices and 1...A faces. Therefore the combinations can be A*A*A.......A = A^N. I think all the guys are in right direction sloving by dynamic programming. But need to add distributed computing based on N. Divide the work and add it like map reduce
public class DiceProblem {
public static void waysToFindSum(int sum, int remainingDices,int[] faces, int[] output,int numberOfDices,int numberOffaces){
if(remainingDices == 0 && sum ==0){
System.out.println("");
for(int i = 0; i < numberOfDices; i++){
System.out.print(output[i]+" ");
}
return;
}
if(remainingDices == 0)
return;
if(sum == 0)
return;
for(int j =0; j< numberOffaces;j++){
if(faces[j] <= sum){
output[remainingDices-1] = faces[j];
waysToFindSum(sum-faces[j], remainingDices-1, faces, output, numberOfDices, numberOffaces);
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
int numberOfDices = 3;
int numberOfFaces = 6;
int sum = 5;
int[] faces = {1,2,3,4,5,6};
int[] output = new int[numberOfDices];
waysToFindSum(sum, numberOfDices, faces, output, numberOfDices,numberOfFaces);
}
}
Recursive solution:
public static int nDiceASum(int N, int A, int S){
if(N<=0) return 0;
if(N==1){
if(S >= 1 && S <= A)
return 1;
else
return 0;
}
int result = 0;
for(int i=1; i<=A; ++i){
result += nDiceASum(N-1, A, S-i);
}
return result;
}
Dynamic Program:
Create 2D matrix with numOfDice, sum on 2 dimensions.
So Matrix[s][n] = Sum( Matrix[s-i][n-1]) for i = 1->A
Initialize first row, first column
Matrix[1][1] = 1;
for(int numDice=2; numDice<n; ++numDice)
Matrix[1][numDice] = 0;
for(int sum=2; sum<S; sum++){
if(sum <= A) Matrix[sum][1] = 1;
else Matrix[sum][1] = 0;
}
Now compute Matrix[Sum][NumDice] to get the result using below loop
for(int s=2; s<=Sum; s++)
for(int n=2; n<=NumDice; n++)
Matrix[s][n] = Sum(Matrix[s-i][n-1]) with i from 1->A;
hi i wrote the below code for this, can anyone please verify this if it fails in any conditionsor any modifications that should be made
public class abs {
private static int[] combos;
public static int sumCombos(int currDice,int faces,int sum){
if(sum > faces && currDice==1){
return -1;
}
if(sum <= faces){
combos[currDice]=sum;
printCombo();
return 0;
}
for(int i=1;i<=faces;i++){
combos[currDice]=i;
sumCombos(currDice-1,faces,(sum-i));
}
return 0;
}
private static void printCombo(){
for(int i=1;i<combos.length;i++){
System.out.print(combos[i]+",");
}
System.out.println();
}
public static void main (String... a){
int noOfDices=4;
int noOfFaces=2;
int totalSum=5;
combos=new int[noOfDices+1];
sumCombos(noOfDices,noOfFaces,totalSum);
}
}
A C# implementation of the recursive solution described in above posts.
public static int DifferentWays(int diceFace, int diceCount, int sum)
{
if (diceCount == 0)
return 0;
if (sum < diceCount) // * 1
return 0;
if (sum > diceCount * diceFace)
return 0;
if (diceCount == 1)
return 1;
int count = 0;
for (int x = 1; x <= diceFace; x++)
{
count += DifferentWays(diceFace, diceCount - 1, sum - x);
}
return count;
}
I got half a solution so far. Let me know if you can get the other half before I do or I give up.
Say you want 13 for a total
And you have 6 dice we won’t worry about the number of faces just yet
If you know that you role 3 ones 2 twos and 1 six you
3 * 1 + 2 * 2 + 1 * 6 = 13 (can I still add?)
We can easily calculate that there are (3+2+1)!/(3!*2!*1!) ways to get it
So we added 60 to the count in one step
If we can quickly iterate through all the combinations of counts of each type of face rather than all the actual sets of roles we might come out ahead.
Know any good algorithm for this
Find all sets of X such that
Such that s is the number of faces
X1* 1 + X2*2 + X3*3 …… Xs * s = total we want
And
X1 + X2 + X3 …… Xs = total number of dice
We could start with X1 as large as possible and then try to make up the difference buy putting values into Xs X(s-1), X(s-2). Then we need some way of transferring value from the high side to the low side without repeating any combinations and without missing any. Probably some loops some recursion and or some dynamic programming as in the solutions above. I think my approach makes the problem smaller in some ways but I am not convinced it really has any advantage when all is told.
If you did a brute force search it would cost O(s^n) perhaps even O(s^(1+n)) if you are lazy about how you calculate the totals to check. This is pretty bad. The complexity of the nice simple naive algorithm is O(n^s) so if n and s are reasonably large and s < n the naïve direct counting is better than the brute force iteration. Dynamic programming is beginning to look very attractive indeed. I think I will try a direct recursive method with dynamic programming.
Any thoughts, you think there is hope for getting through the counts quickly?
I expect that they will ask a different question that needs my half of the answer in combination with some other solution and another question that needs the fast iteration algorithm in combination with yet some other idea: if that makes any sense.
The probability of Occurrence of a sum while throwing a number of dices can be thought of normal distribution.
the probability function would be p(sum). I forgot the formula, article about normal distribution in Wikipedia might help.
After calculating the p(sum), we can multiply the p(sum) by the number of sides power the number of dices
Dynamic Programming solution:
- Vinay April 28, 2013Let Nways(s, n) - number of ways to make sum s with n dices.
Nways(s, n) = Summation{1..a} Nways(s-i, n-1)
Base case:
Nways(s, 1) = 1 if (s<= a && s>0), 0 otherwise.
Edit:
I see lot of new solutions posted are using only recursion. Memoization should be used otherwise the algorithm is very slow.
Recursion with a lookup table for already computed values is the right way to go.