Bloomberg LP Interview Question
Software Engineer / DevelopersTeam: BVal
Country: United States
Interview Type: Phone Interview
This algorithm looks simple but still has time complexity O(N^(M+1)) which is extremely slow . is this the best known solution for this quiz?
This solution doesn't seem to be correct.
I don't get it, but let's try to test it.
If you have 2 dice with 3 sides (as in example), than in the very first iteration of inner cycle, you'll increment m[0]. Since you never decrease any element of m, m[0] at the end of this algorithm can't be less then 1. Although, in the answer the smallest possible sum is 2, and everything below it shold contain 0.
static int numLoops;
static int numIterations;
static int[] loops;
static Map<Integer, Integer> results = new HashMap<Integer, Integer>();
public static void writeHistogram(int numDices, int numSides) {
numLoops = numDices;
numIterations = numSides;
loops = new int[numLoops];
loop(0);
System.out.println();
for (Map.Entry<Integer, Integer> entry : results.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
static void loop(int currentLoop) {
if (currentLoop == numLoops) {
printLoop();
return;
}
for (int counter = 1; counter <= numIterations; counter++) {
loops[currentLoop] = counter;
loop(currentLoop + 1);
}
}
static void printLoop() {
int currentSubtotal = 0;
for (int i = 0; i < numLoops; i++) {
System.out.printf("%d, ", loops[i]);
currentSubtotal += loops[i];
}
System.out.println(" -> " + currentSubtotal);
if (!results.containsKey(currentSubtotal)) {
results.put(currentSubtotal, 1);
} else {
int oldValue = results.get(currentSubtotal);
oldValue++;
results.put(currentSubtotal, oldValue);
}
}
public static void main(String[] args) {
writeHistogram(3, 6);
}
public static void dice(int n, int m, int l) {
// n is number of dice
// m is number of sides
// l is number of dice roll
Map<Integer, Integer> diceFrequency = new HashMap<Integer, Integer>();
Random randomGenerator = new Random();
int result = 0;
for(int nTimes = 0; nTimes < l; nTimes++) {
for (int nDice = 0; nDice < n; nDice++) {
result = result + (randomGenerator.nextInt(m)+1);
}
if(diceFrequency.containsKey(result)) {
diceFrequency.put(result, diceFrequency.get(result)+1);
}
else {
diceFrequency.put(result, 1);
}
result = 0;
}
for (Map.Entry<Integer, Integer> entry : diceFrequency.entrySet()) {
System.out.println(entry.getKey()+": "+entry.getValue());
}
}
code 1 master
.git
code1.cpp
code1.cpp
Run File Save File Search
Ln: 56 Col: 24
C++
OneAll
24
}
25
if ( getResult(resultLast, n-1, m) != 0 ){
26
cout<<"error, can not get the result of N-1 at N="<<n<<endl;
27
return -1;
28
}
29
30
int sum=0;
31
int markOfFront = 0;
32
// assume we got he array of N-1's result array from 0 to resultLastSize
33
for (int i=0; i<resultSize; i++){
34
if (i == 0){
35
result[i] = resultLast[i];
36
}
37
else if (i<m){
38
result[i] = result[i-1] + resultLast[i];
39
}
40
else if (i>=m && i<resultLastSize){
41
result[i] = result[i-1] - resultLast[markOfFront] + resultLast[i];
42
markOfFront++;
43
}
44
else{
45
result[i] = result[i-1] - resultLast[markOfFront];
46
markOfFront++;
47
}
48
}
49
50
free(resultLast);
51
return 0;
52
}
53
54
void show(int* result, int n, int m){
55
cout<<"Showing the result:"<<endl;
56
int resultSize = n*(m-1)+1;
57
for (int i=0; i<resultSize; i++) {
58
cout<<i+n<<" : "<< result[i]<<endl;
59
}
60
}
61
62
63
64
int main() {
65
int n = 3, m = 6;
66
int resultSize = n*(m-1)+1;
67
int *diceResult;
68
69
if ( (diceResult=(int*)malloc(sizeof(int)*resultSize))== NULL ) {
70
cout<<"error, can not allocation memory for Dice; N="<<n<<" , M="<<m<<endl;
71
return -1;
72
}
73
74
getResult(diceResult, n, m);
75
show(diceResult, n, m);
76
free(diceResult);
77
78
cout<<"end of program"<<endl;
79
return 0;
80
}
Toggle the Command Palette - Ctrl + Shift + P
LogsTerminalcode1.cpp
Hello pengzhang130 and welcome to your fully-featured terminal.
Have fun coding on the cloud.
pengzhang130@code 1:/mnt/project$
pengzhang130@code 1:/mnt/project$
pengzhang130@code 1:/mnt/project$ ls
cdoe3.cpp code1.cpp code1.py code2.cpp
pengzhang130@code 1:/mnt/project$ ls
Compiling code1.cpp...
Running code1.cpp...
Compiling code1.cpp...
Running code1.cpp...
f ewfaeafa
^
code1.cpp: In function 'int main()':
code1.cpp:72:52: error: 'alloc' was not declared in this scope
if ( (diceResult=alloc(sizeof(int)*(resultSize)) )== NULL ) {
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.Mh2MEAi3iu: Permission denied
^
code1.cpp: In function 'int main()':
code1.cpp:72:53: error: 'malloc' was not declared in this scope
if ( (diceResult=malloc(sizeof(int)*(resultSize)) )== NULL ) {
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.1kzgRbrZBy: Permission denied
Compiling code1.cpp...
code1.cpp:2:18: fatal error: stdlib: No such file or directory
#include <stdlib>
^
compilation terminated.
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.M2U9m8MG4a: Permission denied
Compiling code1.cpp...
code1.cpp:1:22: fatal error: iostream.h: No such file or directory
#include <iostream.h>
^
compilation terminated.
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.rYyzcAyBgr: Permission denied
Compiling code1.cpp...
code1.cpp:1:22: fatal error: iostream.h: No such file or directory
#include <iostream.h>
^
compilation terminated.
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.MOy5wtT4C5: Permission denied
^
code1.cpp: In function 'int main()':
code1.cpp:74:51: error: invalid conversion from 'void*' to 'int*' [-fpermissive]
if ( (diceResult=malloc(sizeof(int)*resultSize))== NULL ) {
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.V6Ri2JFEg7: Permission denied
^
code1.cpp: In function 'void show(int*, int, int)':
code1.cpp:61:31: error: expected ';' before ')' token
for (int i=0; i<resultSize) {
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.A8OMgrsp59: Permission denied
^
code1.cpp: In function 'void show(int*, int, int)':
code1.cpp:61:31: error: expected ';' before ')' token
for (int i=0; i<resultSize) {
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.tNB17rXDuy: Permission denied
int getResult(int* result, int n, int m){
^
code1.cpp:51:13: error: expected ';' before 'markOfFront'
markOfFront++;
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.H3fYRRDzJH: Permission denied
if ( getResult(resultLast, resultLastSize, n-1, m) != 0 ){
^
code1.cpp:8:5: note: declared here
int getResult(int* result, int n, int m){
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.A1IpgwDsl6: Permission denied
Compiling code1.cpp...
code1.cpp: In function 'int getResult(int*, int, int)':
code1.cpp:22:39: error: expected ',' or ';' before ')' token
int resultLastSize = (n-1)*(m-1)+1);
^
Running code1.cpp...
/usr/local/bin/run: line 51: /tmp/tmp.KBQYWzBd9Q: Permission denied
Compiling code1.cpp...
Running code1.cpp...
Compiling code1.cpp...
Running code1.cpp...
Compiling code1.cpp...
Running code1.cpp...
call get result for N=2 , M=3
call get result for N=1 , M=3
Compiling code1.cpp...
Running code1.cpp...
call get result for N=2 , M=3
call get result for N=1 , M=3
Compiling code1.cpp...
Running code1.cpp...
call get result for N=2 , M=3
call get result for N=1 , M=3
reach n =0, end loop.
Showing the result:
1 : 1
2 : 2
3 : 3
4 : 2
5 : 1
end of program
6 : 6
7 : 5
8 : 4
9 : 3
10 : 2
11 : 1
end of program
7 : 6
8 : 5
9 : 4
10 : 3
11 : 2
12 : 1
end of program
13 : 21
14 : 15
15 : 10
16 : 6
17 : 3
18 : 1
end of program
#include <iostream>
#include <stdlib.h>
using namespace std;
// result will be a int array of size from 0 to n*(m-1)+1
int getResult(int* result, int n, int m){
int resultSize = n*(m-1)+1;
if ( n==1 ){
for (int i=0; i<resultSize; i++){
result[i] = 1;
}
cout<<"reach n=0, end loop."<< endl;
return 0;
}
int resultLastSize = (n-1)*(m-1)+1;
// get the result of n-1
int *resultLast;
if ( (resultLast=(int*)malloc(sizeof(int)*(resultLastSize)) )== NULL ) {
cout<<"error, can not allocation memory at N="<<n<<endl;
return -1;
}
if ( getResult(resultLast, n-1, m) != 0 ){
cout<<"error, can not get the result of N-1 at N="<<n<<endl;
return -1;
}
int sum=0;
int markOfFront = 0;
// assume we got he array of N-1's result array from 0 to resultLastSize
for (int i=0; i<resultSize; i++){
if (i == 0){
result[i] = resultLast[i];
}
else if (i<m){
result[i] = result[i-1] + resultLast[i];
}
else if (i>=m && i<resultLastSize){
result[i] = result[i-1] - resultLast[markOfFront] + resultLast[i];
markOfFront++;
}
else{
result[i] = result[i-1] - resultLast[markOfFront];
markOfFront++;
}
}
free(resultLast);
return 0;
}
void show(int* result, int n, int m){
cout<<"Showing the result:"<<endl;
int resultSize = n*(m-1)+1;
for (int i=0; i<resultSize; i++) {
cout<<i+n<<" : "<< result[i]<<endl;
}
}
int main() {
int n = 3, m = 6;
int resultSize = n*(m-1)+1;
int *diceResult;
if ( (diceResult=(int*)malloc(sizeof(int)*resultSize))== NULL ) {
cout<<"error, can not allocation memory for Dice; N="<<n<<" , M="<<m<<endl;
return -1;
}
getResult(diceResult, n, m);
show(diceResult, n, m);
free(diceResult);
cout<<"end of program"<<endl;
return 0;
}
How about a dynamic programming method. Make the observation that any value in the range n - n*sides must be reachable as a summation of other summations. IE:
f(m, d) = sum{i = 1 .. sides} (if (i >= n) then f(n-i, d-1) else (0)) with base case
f(m, 1) = m
Complexity would be O(d * (d * n ^ 2 - (d -1) ) ) which is roughly O( d^2 * n ^2) with memory cost of O( d * n - (d -1) ) which is roughly O (d * n) where d is the number of dice and n is the number of sides.
public static void computeTotalSums(int numSides, int numDice){
int[] sums = new int[numSides];
for(int i = 0; i < sums.length; i++){
sums[i] = 1;
}
int offset = 0;
if(numDice > 1){
for(int dice = 2; dice <= numDice; dice++){
offset = dice -1;
int[] nextSums = new int[dice * numSides - offset];
for(int i = 0; i < nextSums.length; i++){
int sum = 0;
int sum = 0;
for(int side = 0; side < numSides; side++){
int sumsIndex = i - side;
if(sumsIndex > -1 && sumsIndex < sums.length){
sum += sums[sumsIndex];
}
}
nextSums[i] = sum;
}
sums = nextSums;
}
}
for(int i = 0; i < sums.length; i++){
System.out.println(""+(offset+i+1)+": "+sums[i]);
}
}
I used a hash map to store all possible values and wrote a recursive function called roll that would generate all the possible combinations and store the value of those combinations into the hash map. Afterwards, I know that the minimum value is always the number of dice (since minimum side value is 1) and that maximum value is number of dice * number of sides. I wrote a for loop to go from min to max values to print out from the hash map.
#include <iostream>
#include <map>
using namespace std;
map<int,int> m;
void roll(int val, int numOfDice, int numOfSides)
{
if(numOfDice==0)
{
m[val]+=1;
}
else
{
for (int i=1;i<=numOfSides;i++)
{
roll(val+i,numOfDice-1,numOfSides);
}
}
}
void getDicePermutations(int numOfDice, int numOfSides)
{
roll(0,numOfDice,numOfSides);
for (int i=numOfDice;i<=numOfDice*numOfSides;i++)
{
cout << i << ": " << m[i] << endl;
}
}
int main()
{
getDicePermutations(3,3);
}
#include <cstdlib>
#include <iostream>
using namespace std;
void func1(int m, int n);
int main(int argc, char** argv) {
int m, n;
cout<<"Enter m: ";
cin>>m;
cout<<"Enter n: ";
cin>>n;
cout<<endl;
func1(m, n);
return 0;
}
void func1(int m, int n){
int* a = new int[n+m-1];
for(int i = 0; i < n+m-1; i++)
a[i]=0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i+j-2]++;
for(int i = 0; i < n+m-1; i++)
cout<< i+2 <<" : "<< a[i] << endl;
delete [] a;
}
private static HashMap<Integer, Integer> getMap(int n, int m, HashMap<Integer, Integer> map) {
for(int k = 1; k<= m; k++){ // fill for first die
map.put(k, 1);
}
for(int i=1;i<n; i++){ // now calc for remaining n-1 die
HashMap<Integer,Integer> temp = new HashMap<Integer,Integer>();
for( int j = 1; j<= m; j++){
for(int val : map.keySet()){
int times = map.get(val);
int newVal = val + j;
if(temp.containsKey(newVal))
temp.put(newVal,temp.get(newVal) + times);
else
temp.put(newVal, times);
}
}
map = temp;
}
return map;
}
package com.ashok.pattern;
import java.io.*;
import java.lang.Math;
public class DiceProblem {
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please Enter the value of m and n :");
int m=Integer.parseInt(br.readLine());
int n=Integer.parseInt(br.readLine());
int count=0;
int k=0,l=0;
int arr[]=new int[n*n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
arr[k]=(i+1)+(j+1);
System.out.println("("+(i+1)+ " "+","+(j+1)+ " )"+"->"+((i+1)+(j+1)));
k++;
}
}
for(int i=0;i<n*n;i++)
{
for(int j=0;j<n*n;j++)
{
if(arr[i]==arr[j])
{
count++;
}
if(j==(n*n)-1 )
{
System.out.println(arr[i]+" :"+count);
}
}
count=0;
}
}
}
package com.ashok.pattern;
import java.io.*;
import java.lang.Math;
public class DiceProblem {
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please Enter the value of m and n :");
int m=Integer.parseInt(br.readLine());
int n=Integer.parseInt(br.readLine());
int count=0;
int k=0,l=0;
int arr[]=new int[n*n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
arr[k]=(i+1)+(j+1);
System.out.println("("+(i+1)+ " "+","+(j+1)+ " )"+"->"+((i+1)+(j+1)));
k++;
}
}
for(int i=0;i<n*n;i++)
{
for(int j=0;j<n*n;j++)
{
if(arr[i]==arr[j])
{
count++;
}
if(j==(n*n)-1 )
{
System.out.println(arr[i]+" :"+count);
}
}
count=0;
}
}
}
package com.ashok.pattern;
import java.io.*;
import java.lang.Math;
public class DiceProblem {
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please Enter the value of m and n :");
int m=Integer.parseInt(br.readLine());
int n=Integer.parseInt(br.readLine());
int count=0;
int k=0,l=0;
int arr[]=new int[n*n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
arr[k]=(i+1)+(j+1);
System.out.println("("+(i+1)+ " "+","+(j+1)+ " )"+"->"+((i+1)+(j+1)));
k++;
}
}
for(int i=0;i<n*n;i++)
{
for(int j=0;j<n*n;j++)
{
if(arr[i]==arr[j])
{
count++;
}
if(j==(n*n)-1 )
{
System.out.println(arr[i]+" :"+count);
}
}
count=0;
}
}
}
void DiceCountSum(int n, int m, std::map<int, int> &histogram, int sum)
{
if(n == 1)
{
for(int i = 1; i <= m; ++i)
histogram[sum + i]++;
return ;
}
for(int i = 1;i <= m; ++i)
{
DiceCountSum(n - 1, m, histogram, sum + i);
}
}
//call it like
// std::map<int, int> histogram;
// DiceCountSum(3, 6, histogram, 0);
DP Solution: o(n3)
void DiceCountSumDP(int n, int m)
{
//int table[n + 1][m + 1]; // 0 0 entries never used.
static int table[3][7]; // 2 dice, 3 face. 6 + 1
for(int i = 1 ; i <= m; ++i) // for a single dice.
{
table[1][i] = 1;
}
for(int i = 1; i <= n *m; ++i) // for n *m sums
{
for(int j = 2; j <= n; ++j) // for n dices
{
for(int k = 1; k <= m; ++k) // for kth face
{
if(i >= k)
table[j][i] += table[j - 1][i - k];
}
}
}
for(int i = 1 ; i < 3; ++i) // for a single dice.
{
for(int ii = 1 ; ii < 7; ++ii) // for a single dice.
{
cout<<table[i][ii]<<", ";
}
cout<<endl;
}
}
counts = 0
def find_combinations (S, D, N, curr_n=0, curr_d=0):
global counts
if curr_d==0:
counts=0
#print '-'*4, curr_n, curr_d
if curr_d<=D:
for i in range(1,S+1,1):
#print ' '*curr_d, i
if (curr_n+i==N and curr_d+1 == D):
counts = counts+1
#print '#'
else:
if (curr_n+i<N and (curr_d+1)<D):
r = find_combinations(S,D,N, curr_n+i, curr_d+1)
return counts
for j in range(1,10):
print j, find_combinations(3,2,j)
public class Solution {
public static void diceHist(int numDice, int numSides){
int [] res = new int[numDice*numSides-numDice+1];
helper(res, numDice, numSides, 0, 0);
for(int i=0;i<res.length;i++){
System.out.println(i+numDice+":"+res[i]);
}
}
public static void helper(int[] res, int numDice, int numSides, int curIndex, int curSum){
if(curIndex==numDice){
res[curSum-numDice]++;
return;
}
for(int i=1;i<=numSides;i++){
curSum+=i;
helper(res,numDice,numSides,curIndex+1,curSum);
curSum-=i;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
diceHist(2,3);
}
}
Below is recursive solution in C#
public void ProcessDice(int currentDiceIndex, int[] currentDiceRollValues)
{
if (currentDiceIndex >= Dices)
{
int sum = 0;
for (int i = 0; i < currentDiceRollValues.Length; i++)
{
sum = sum + currentDiceRollValues[i];
}
if (!HistogramValues.ContainsKey(sum))
{
HistogramValues.Add(sum,1);
}
else
{
HistogramValues[sum] = HistogramValues[sum] + 1;
}
return;
}
else
{
for (int i = 1; i <= Sides ; i++)
{
currentDiceRollValues[currentDiceIndex] = i;
ProcessDice(currentDiceIndex + 1, currentDiceRollValues);
}
}
}
Here is the recursive solution in C++.
The first parameter maps dice sums to number of occurrences.
In this function, the recursion is over each die.
void DiceDist2
(
map<unsigned, unsigned>& m,
unsigned numDice,
unsigned numSides,
unsigned partialSum = 0
)
{
unsigned u = 1;
if (numDice == 1) while (u <= numSides)
++m[partialSum + u++];
else while(u <= numSides)
DiceDist2(m, numDice - 1, numSides, partialSum + u++);
}
Using R.
rollDice <- function(dice = 2, sides = 3){
a <- expand.grid(replicate(dice, 1:sides, simplify=FALSE))
hist(rowSums(a), breaks = 1:6)
}
#include <iostream>
using namespace std;
int n = 2;
int m=3;
void print( int arr[]){
int i;
int sum = 0;
for(i=0; i<n; i++){
sum = sum + arr[i];
}
cout << sum << endl;
}
void recFunc( int arr[], int index ){
if( index == n ){
print(arr);
return;
}
int i;
for(i=1; i<=m; i++){
arr[index] = i;
recFunc(arr, index+1);
}
}
void recWrap(){
int arr[n];
recFunc( arr, 0 );
}
int main() {
// your code goes here
recWrap( );
return 0;
}
void ndicekside(int n, int k){
int size=pow(k, n);
int j,del,sum;
unordered_map<int, int> m;
vector<int> throws(n);
for (int i=0; i<size; ++i) {
del=i;
j=(int)throws.size()-1;
for (int u=0; u<n; ++u) {
throws[j]=del%k+1;
del/=k;
--j;
}
sum=0;
for (int t=0; t<throws.size(); ++t) {
sum+=throws[t];
}
m[sum]+=1;
}
cout<<"out:"<<endl;
for (auto y=m.begin(); y!=m.end(); ++y) {
cout<<"("<<y->first<<","<<y->second<<")"<<endl;
}
}
public class Dice{
public static void main(String [] args){
int A[]=new int[9];
int k=0;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
A[k]=i+j;
k++;
}
}
System.out.println("--- Output ---");
for(int i=1;i<=6;i++){
int m=0;
for(int j=0;j<9;j++){
if(i==A[j])
m++;
}
System.out.print(" "+i+" times : "+m);
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include<vector>
class Node
{
public:
std::map<int, int> m;
int NumDice = 6;
int NumSides = 6;
void CalculateFreq(int Sum, int Count)
{
if (Count == NumDice)
++m[Sum];
else
{
for (int i = 1; i <= NumSides; i++)
CalculateFreq(Sum + i, Count + 1);
}
}
void PrintFreq()
{
for (std::map<int, int >::iterator it = m.begin(); it != m.end(); ++it)
{
printf("%d: %d\n", it->first, it->second);
}
}
};
int main(int argc, char * argv[])
{
Node * NewNode = new Node();
NewNode->CalculateFreq(0, 0);
NewNode->PrintFreq();
}
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
HashMap<Integer,Integer> map = getHist(3,3);
System.out.println(map.get(3));
System.out.println(map.get(4));
System.out.println(map.get(5));
System.out.println(map.get(6));
System.out.println(map.get(7));
System.out.println(map.get(8));
System.out.println(map.get(9));
}
public static HashMap<Integer,Integer> getHist(int n, int m)
{
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
map.put(n,1);
map.put(n+1,n);
int mid = (n+n*m)/2;
for(int i= n+2; i<= n*m ; i++)
{
if(i<=mid)
{
int dif = i - n;
int sum=0;
for(int j=0;j<dif;j++)
{
sum += map.get(n+j);
}
map.put(i,sum);
}
else
{
int dif = i - mid;
map.put(i,map.get(mid-dif));
}
}
return map;
}
}
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <map>
using namespace std;
#define loop(x,n) for(int x=0; x<n; x++)
int main(){
int nsides = 6;
int ndices = 3;
int* vface = (int*)calloc(nsides,sizeof(int));
loop(i,nsides)
vface[i] = i+1;
vector<int> vSum(vface,vface+nsides);
vector<int> vtemp;
loop(i,ndices-1)
{
vtemp = vector<int>(vSum);
vSum.erase(vSum.begin());
loop(j,nsides)
{
if(j==0) continue;
loop(k,vtemp.size())
vSum.push_back(vtemp[k]+vface[j]);
}
}
vtemp.erase(vtemp.begin());
map<int,int>hist;
loop(i,vSum.size())
if(hist.count(vSum[i]) >0)
hist[vSum[i]] += 1;
else
hist[vSum[i]] = 1;
for(map<int,int>::iterator it = hist.begin(); it != hist.end(); it++)
cout<<it->first<<"\t"<<it->second<<endl;
}
Complexity( face^dice)
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <map>
using namespace std;
#define loop(x,n) for(int x=0; x<n; x++)
int main(){
int nsides = 6;
int ndices = 3;
int* vface = (int*)calloc(nsides,sizeof(int));
loop(i,nsides)
vface[i] = i+1;
vector<int> vSum(vface,vface+nsides);
vector<int> vtemp;
loop(i,ndices-1)
{
vtemp = vector<int>(vSum);
vSum.erase(vSum.begin());
loop(j,nsides)
{
if(j==0) continue;
loop(k,vtemp.size())
vSum.push_back(vtemp[k]+vface[j]);
}
}
vtemp.erase(vtemp.begin());
map<int,int>hist;
loop(i,vSum.size())
if(hist.count(vSum[i]) >0)
hist[vSum[i]] += 1;
else
hist[vSum[i]] = 1;
for(map<int,int>::iterator it = hist.begin(); it != hist.end(); it++)
cout<<it->first<<"\t"<<it->second<<endl;
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class Histogram {
public Histogram() {
int n = 3;
int m = 3;
generateHistogram (n,m);
}
private void generateHistogram(int n, int m) {
HashMap<Integer, ArrayList<Values>> map = new HashMap<Integer, ArrayList<Values>>();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if(map.containsKey(i+j)){
ArrayList<Values> arr = map.get(i+j);
Values val = new Values(i, j);
arr.add(val);
map.put(i+j, arr);
}else{
Values val = new Values(i, j);
ArrayList<Values> arr = new ArrayList<Values>();
arr.add(val);
map.put(i+j, arr);
}
}
}
Set<Integer> keySet = map.keySet();
Iterator<Integer> objIterator = keySet.iterator();
while(objIterator.hasNext()){
int temp = (int) objIterator.next();
ArrayList<Values> arr = map.get(temp);
System.out.println(temp + ": " + arr.size());
}
}
public class Values {
int a;
int b;
Values(int a, int b){
this.a = a;
this.b = b;
}
}
}
#include <iostream>
#include <vector>
#include <iterator>
void diceHist(unsigned dices, unsigned sides, std::vector<unsigned> &hist, unsigned prevSum) {
if (dices == 0) {
++hist[prevSum];
return;
}
for (int i = 1; i <= sides; ++i) {
diceHist(dices-1, sides, hist, i+prevSum);
}
}
// just to display result
void display_vector(const std::vector<unsigned> &v)
{
std::copy(v.begin(), v.end(),
std::ostream_iterator<unsigned>(std::cout, " "));
}
int main() {
int dices = 3;
int sides = 3;
std::vector<unsigned> hist(dices*sides +1, 0);
diceHist(dices, sides, hist, 0);
display_vector(hist);
return 0;
}
/*
* Given n fair dice with m side, return the histogram of frequency of their sum.
*/
public class DiceRollHistogram {
public static Map<Integer, Integer> getHistogram(int n, int m) {
Map<Integer, Integer> histogram = new HashMap<Integer, Integer>();
int[] a = new int[n];
Arrays.fill(a, 1);
while (true) {
try {
int sum = computeSum(a);
if (histogram.containsKey(sum)) {
histogram.put(sum, histogram.get(sum) + 1);
} else {
histogram.put(sum, 1);
}
a = incermentCounter(a, m);
} catch (OverFlowExecution e) {
break;
}
}
return histogram;
}
private static int computeSum(int[] a) {
int count = 0;
for (int i = 0; i < a.length; i++) {
count += a[i];
}
return count;
}
private static int[] incermentCounter(int[] a, int m) {
if (isMax(a, m))
throw new OverFlowExecution();
for (int i = 0; i < a.length; i++) {
if (a[i] == m) {
a[i] = 1;
continue;
} else {
a[i] = a[i] + 1;
break;
}
}
return a;
}
private static boolean isMax(int[] a, int m) {
for (int i = 0; i < a.length; i++) {
if (a[i] < m)
return false;
}
return true;
}
public static void main(String[] args) {
Map<Integer, Integer> histogram = DiceRollHistogram.getHistogram(2, 3);
System.out.println(histogram.size());
}
}
class OverFlowExecution extends RuntimeException {
private static final long serialVersionUID = -3553581134335170678L;
}
/*
* Given n fair dice with m side, return the histogram of frequency of their sum.
*/
public class DiceRollHistogram {
public static Map<Integer, Integer> getHistogram(int n, int m) {
Map<Integer, Integer> histogram = new HashMap<Integer, Integer>();
int[] a = new int[n];
Arrays.fill(a, 1);
while (true) {
try {
int sum = computeSum(a);
if (histogram.containsKey(sum)) {
histogram.put(sum, histogram.get(sum) + 1);
} else {
histogram.put(sum, 1);
}
a = incermentCounter(a, m);
} catch (OverFlowExecution e) {
break;
}
}
return histogram;
}
private static int computeSum(int[] a) {
int count = 0;
for (int i = 0; i < a.length; i++) {
count += a[i];
}
return count;
}
private static int[] incermentCounter(int[] a, int m) {
if (isMax(a, m))
throw new OverFlowExecution();
for (int i = 0; i < a.length; i++) {
if (a[i] == m) {
a[i] = 1;
continue;
} else {
a[i] = a[i] + 1;
break;
}
}
return a;
}
private static boolean isMax(int[] a, int m) {
for (int i = 0; i < a.length; i++) {
if (a[i] < m)
return false;
}
return true;
}
public static void main(String[] args) {
Map<Integer, Integer> histogram = DiceRollHistogram.getHistogram(2, 3);
System.out.println(histogram.size());
}
}
class OverFlowExecution extends RuntimeException {
private static final long serialVersionUID = -3553581134335170678L;
}
/*
Given n > 0 fair dice with m > 0 "sides", write a function that returns a histogram of the
frequency of the result of dice rolls. For example, for two dices, each with three sides, the
results are:
*/
void combine(map<int,int>& result, const vector<int>& sides){
if(result.empty()){
vector<int>::const_iterator it;
for (it = sides.begin(); it != sides.end(); ++it){
result.insert(pair<int,int>(*it, 1));
}
return;
}
map<int,int> newResult;
map<int,int>::iterator itMap;
vector<int>::const_iterator itVct;
for (itVct = sides.begin(); itVct != sides.end(); ++itVct){
for (itMap = result.begin(); itMap != result.end(); ++itMap){
int num = itMap->first + (*itVct);
map<int,int>::const_iterator it = newResult.find(num);
if (it == newResult.end()){
newResult.insert(pair<int,int>(num, 1));
}
else {
newResult[num]++;
}
}
}
result = newResult;
}
void processDices(map<int,int>& result, int dice, int side){
vector<int> sides;
for (int i=1; i<=side; ++i){
sides.push_back(i);
}
for (int i=0; i<dice; ++i){
combine(result, sides);
}
}
void Question_2(){
map<int,int> testMap;
processDices(testMap, 4, 4);
map<int,int>::iterator it;
for (it = testMap.begin(); it != testMap.end(); ++it){
cout << it->first << " : " << it->second << endl;
}
}
/*
Given n > 0 fair dice with m > 0 "sides", write a function that returns a histogram of the
frequency of the result of dice rolls. For example, for two dices, each with three sides, the
results are:
*/
void combine(map<int,int>& result, const vector<int>& sides){
if(result.empty()){
vector<int>::const_iterator it;
for (it = sides.begin(); it != sides.end(); ++it){
result.insert(pair<int,int>(*it, 1));
}
return;
}
map<int,int> newResult;
map<int,int>::iterator itMap;
vector<int>::const_iterator itVct;
for (itVct = sides.begin(); itVct != sides.end(); ++itVct){
for (itMap = result.begin(); itMap != result.end(); ++itMap){
int num = itMap->first + (*itVct);
map<int,int>::const_iterator it = newResult.find(num);
if (it == newResult.end()){
newResult.insert(pair<int,int>(num, 1));
}
else {
newResult[num]++;
}
}
}
result = newResult;
}
void processDices(map<int,int>& result, int dice, int side){
vector<int> sides;
for (int i=1; i<=side; ++i){
sides.push_back(i);
}
for (int i=0; i<dice; ++i){
combine(result, sides);
}
}
void Question_2(){
map<int,int> testMap;
processDices(testMap, 4, 4);
map<int,int>::iterator it;
for (it = testMap.begin(); it != testMap.end(); ++it){
cout << it->first << " : " << it->second << endl;
}
}
/*
Given n > 0 fair dice with m > 0 "sides", write a function that returns a histogram of the
frequency of the result of dice rolls. For example, for two dices, each with three sides, the
results are:
*/
void combine(map<int,int>& result, const vector<int>& sides){
if(result.empty()){
vector<int>::const_iterator it;
for (it = sides.begin(); it != sides.end(); ++it){
result.insert(pair<int,int>(*it, 1));
}
return;
}
map<int,int> newResult;
map<int,int>::iterator itMap;
vector<int>::const_iterator itVct;
for (itVct = sides.begin(); itVct != sides.end(); ++itVct){
for (itMap = result.begin(); itMap != result.end(); ++itMap){
int num = itMap->first + (*itVct);
map<int,int>::const_iterator it = newResult.find(num);
if (it == newResult.end()){
newResult.insert(pair<int,int>(num, 1));
}
else {
newResult[num]++;
}
}
}
result = newResult;
}
void processDices(map<int,int>& result, int dice, int side){
vector<int> sides;
for (int i=1; i<=side; ++i){
sides.push_back(i);
}
for (int i=0; i<dice; ++i){
combine(result, sides);
}
}
void Question_2(){
map<int,int> testMap;
processDices(testMap, 4, 4);
map<int,int>::iterator it;
for (it = testMap.begin(); it != testMap.end(); ++it){
cout << it->first << " : " << it->second << endl;
}
}
Do it using DP. start with 1 to n dice and m sides. Suppose we have 3 dice with 3 sides. Then we start loop with 1 to 3 for first die we have sums [1,2,3] --> just 1 die involved, for second die we get sums like [(1+1),(1+2),(1+3),(2+1),(2+2),...,(3+2),(3+3)] similarly we iterate for 3 die and we get sums as [(1+1+1),(1+1+2),....,(3+3+3)] total m^n sums. Complexity of this solution is O(m*n). We can use hashmap to store sum to reduce space complexity.
- Aurelius October 29, 2014