Bloomberg LP Interview Question for Software Engineer / Developers


Team: BVal
Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
4
of 4 vote

// here is the non-recursive solution

void DiceDist(map<unsigned, unsigned>& m, unsigned numDice, unsigned numSides)
{
    vector<unsigned> vec(numDice, 1);

    bool looptest = true;
    while (looptest)
    {
        unsigned sum = 0;
        for (unsigned u = 0; u < numDice; ++u) sum += vec[u];
            ++m[sum];

        unsigned i = 0;
        while (looptest && ++vec[i] > numSides)
        {
            vec[i] = 1;
            if (++i == numDice)
                looptest = false;
        }
    }
}

- Aurelius October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Excellent!!

- aashcool198 November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Ian February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous February 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote
Something similar : {{{ #include <iostream> #include <vector> #include <unordered_map> using namespace std; unordered_map<int, int> getFreqMap(int m, int n) { unordered_map<int, int> freq; vector<int> freq_vec; for (int i = 1; i <= n; ++i) { freq_vec.push_back(i); } for (int i = 2; i <= m; ++i) { vector<int> new_vec; for (int k = 0; k < freq_vec.size(); ++k) { for (int j = 1; j <= n; ++j) { new_vec.push_back(freq_vec[k]+j); } } freq_vec = new_vec; } for (int i = 0; i < freq_vec.size(); ++i) { freq[freq_vec[i]]++; } return freq; } typedef unordered_map<int,int>::iterator It; void printMap(unordered_map<int,int>& freq){ for (It it= freq.begin(); it != freq.end(); ++it) { cout << it->first << " : " << it->second << "\n"; } cout << "************************************\n"; } int main() { unordered_map<int, int > freq = getFreqMap(3,2); printMap(freq); freq = getFreqMap(2,3); printMap(freq); freq = getFreqMap(3,3); printMap(freq); } }} - anonymous March 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }

- IgorBrown31 October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is not correct for number of dice greater than 2.

- Aurelius October 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Fixed, thanks. Slightly (<- strikethrough) cumbersome code, but it should work now.

- IgorBrown31 October 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code

def LinList(lst):
    if isinstance(lst,type(list())):
        for i in lst:
            for y in LinList(i):
                yield y
    else:
        yield lst

d=[[2,3,4],[3,4,5],[4,5,6]]
a=[y for y in LinList(d)]
c=dict()
for x in set(a):
    c[x]=a.count(x)
for x in c.keys():
    print x,":",c[x]

- Rost October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
		}        
}

- Yulduz October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please ignore and remove this.

- pzhang.pn October 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- pzhang.pn October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
    }
}

- zortlord October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def s(n, m):
    stat = 0
    half = (n + m * n) / 2
    isOdd = (n + m * n) % 2 == 1
    for i in range(n, m*n + 1):
        if i > half:
            if isOdd:
                isOdd = False
            else:
                stat -= 1
        else:
            stat += 1
        yield (i, stat)

- Ivan October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Simmon Yau November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;   
}

- shone43 November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ryavied November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- ashok singh November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- ashok singh November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- ashok singh November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous November 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous November 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you think you need a DP solution for this? This problem is O(dice * sides). And you cannot use magic numbers 3 and 7. These are parameters.

- Aurelius November 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Zaigham November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

}

- leizhous November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
				}
			}
		}

- Vik November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you fix the formatting on this? It's hard to read.

- Aurelius November 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++);
}

- Aurelius November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using R.

rollDice <- function(dice = 2, sides = 3){
 a <- expand.grid(replicate(dice, 1:sides, simplify=FALSE)) 
 hist(rowSums(a), breaks = 1:6)
}

- Josh November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

To make the histogram robust I should have put

hist(rowSums(a), breaks = 1:(sides*dice))

- Josh November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Hawkein November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- andrey November 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}
}

- sadhanaj28 December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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();
}

- Anonymous December 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int len = m*n-m+1;
vector<int> ret(len, 0);
int a = 1;
for(int i = 0; i<len/2+1;i++)
{
ret[i] = ret[len-1-i] = a;
a+=m-1;
}
return ret;

- Anonymous January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int len = m*n-m+1;
vector<int> ret(len, 0);
int a = 1;
for(int i = 0; i<len/2+1;i++)
{
ret[i] = ret[len-1-i] = a;
a+=m-1;
}
return ret;

- anna January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int len = m*n-m+1;
vector<int> ret(len, 0);
int a = 1;
for(int i = 0; i<len/2+1;i++)
{
	ret[i] = ret[len-1-i] = a;
	a+=m-1;
}
return ret;

- anna January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- naomi.lijing@googlemail.com February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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)

- max March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- max March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It says just print, not calculate. For each dice, order is same. It becomes apparent with just a little attention.

def freq(n):
        inc = ""
        dec = ""
        for i in xrange(1,n+1):
                inc += str(i) + "\n"
                dec += str(n+1 - i) + "\n"
        print (inc+dec[2:])

freq(5)

- o(n) - easy implementation June 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- IG July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* 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;

}

- Shivam Maharshi October 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * 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;

}

- Shivam Maharshi October 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
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;
}
}

- Jupon June 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
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;
}
}

- Jupon June 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
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;
}
}

- Jupon June 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- 256.cool October 19, 2016 | 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