Aurelius
BAN USER- 2of 2 votes
Answersgiven n > 0 fair dice with m > 0 "sides", write an function that returns a histogram of the frequency of the result of dice rolls. For example, for two dice, each with three sides, the results are:
- Aurelius in United States for BVal
(1, 1) -> 2
(1, 2) -> 3
(1, 3) -> 4
(2, 1) -> 3
(2, 2) -> 4
(2, 3) -> 5
(3, 1) -> 4
(3, 2) -> 5
(3, 3) -> 6
And the function should return:
2: 1
3: 2
4: 3
5: 2
6: 1| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Coding
- 0 Answers CTCI Question 2.5 - add linked lists
The answer in the book is not terribly compact, especially for part 2. Here is a better version in C++.
- Aurelius December 07, 2014
Node * list_add(Node * pN0, Node * pN1)
{
Node * pNReturn = nullptr;
Node ** ppNNext = & pNReturn;
unsigned carry = 0;
while (pN0 != nullptr || pN1 != nullptr || carry > 0)
{
unsigned sum = carry;
if (pN0 != nullptr)
{
sum += pN0->data;
pN0 = pN0->next;
}
if (pN1 != nullptr)
{
sum += pN1->data;
pN1 = pN1->next;
}
if (sum >= 10)
{
sum -= 10;
carry = 1;
}
else
{
carry = 0;
}
*ppNNext = new Node;
(*ppNNext)->data = sum;
(*ppNNext)->next = nullptr;
ppNNext = &(*ppNNext)->next;
}
return pNReturn;
}
// helper function
Node * list_reverse(Node * pNHead)
{
Node * pNRet = pNHead;
if (pNHead != nullptr && pNHead->next != nullptr)
{
Node * pN0 = pNHead, * pN1 = pNHead->next;
pN0->next = nullptr;
while (pN1 != nullptr)
{
Node * pNHold = pN1->next;
pN1->next = pN0;
pN0 = pN1;
pN1 = pNHold;
}
pNRet = pN0;
}
return pNRet;
}
// Now part 2 becomes a piece of cake
Node * list_add2(Node * pNHead0, Node * pNHead1)
{
return list_reverse(list_add(list_reverse(pNHead0), list_reverse(pNHead1)));
}| Flag | PURGE
// 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;
}
}
}
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.
- Aurelius November 13, 2014