## Sunday, July 24, 2016

### google interview: compute the minual coins

Over all the result of this one is workable but I expect that there should be a way equal the greedy's performance in the asymptotic, because the fine details of least significant numbers have stop changing once you get far enough out of range of the largest coin.. hence it seems very plausible there is is a better algorithm larger numbers... I just dont have the time to work it out, maybe something that greedy guesses the largest coin value to some limit and then does the real search for the rest..

Update: I have just found some more time and added one more improvement that cuts of more time (bottom up to reachable only) .. i had another improvement in mind (reachable + astar distance until end via max usable coin).. BUT this had 2 issues the astar is a greedy so not perfect and the use of a priority queue added significant overhead, destroying all benefit of it anyway..

Update2: I cracked the asymptotic constant version.. kicks these out of the room.. check out http://code-slim-jim.blogspot.com/2016/07/google-interview-compute-mininual-coins.html (next post after this one)

// http://www.impactinterview.com/2009/10/140-google-interview-questions/#software_engineer
//
// Given a set of coin denominators, find the minimum number of coins to give a
// certain amount of change.

#include <cstdint>
#include <climits>
#include <vector>
#include <iostream>
#include <functional>
#include <chrono>
#include <memory>
#include <list>

// This question is quite interesting, even though it simple to ask the range
// of potential solutions is wide as far as i see it you have 2 main choices:
// 1) you can treat it as a graph and perform BFS, astar, etc to search on it
// 2) you can treat it as a recursion and dynamic programming question

// Given that this can form a tree you can also use greedy search to find a
// solution.  BUT since you are searching for the *minimal* length the result
// from greedy is likely to be sub optimal.

// Also note that we can have multiple solutions to the problem depending on
// value and denominations 6 => 1+5 = 2+4 = ...  etc
// Its also possible to have no solutions (for example exclude 1 from the denominations)

// So lets get started
// A greedy implementation - a quick greedy way to the answer is to maximize
// the largest coin
//
// Note this can give the *wrong* answer
// Note expects reverse sorted coins (largest to smallest)
std::vector<uint32_t> minCoins_greedy(uint32_t total,
const std::vector<uint32_t>& denom)
{
std::vector<uint32_t> res(denom.size()+1,0);

if (total == 0) return res;

for(int i = 0; i < denom.size(); ++i)
{
uint32_t count = total / denom[i];
total -= (count * denom[i]);

res[i] = count;
res[denom.size()] += count;
}

if (total != 0) res[denom.size()] = INT_MAX;

return res;
}

// The recursive implementation - simply walk the entire tree of possibilities
// First we need to formulate the induction.  We will add one coin each time
// and then recurse.  Hence the induction v[n] number of coins for total n is:
//   v[n] = 1 + v[n - c]
//
// Note denoms need to be in reverse order.. max to min!
std::vector<uint32_t> minCoins_naive(uint32_t total,
const std::vector<uint32_t>& denom)
{
std::vector<uint32_t> res(denom.size()+1,0);

if (total == 0) return res;

res[denom.size()] = INT_MAX;

for(int i = 0; i < denom.size(); ++i)
{
if (total >= denom[i])
{
std::vector<uint32_t> pass = minCoins_naive(total - denom[i],
denom);

if ((pass[denom.size()]  + 1) < res[denom.size()])
{
res = pass;
++(res[i]);
++(res[denom.size()]);
}
}
}

return res;
}

// Now the naive recursion is also computing items that we know are already
// larger than our current known best min hence we can the prune tree here -
// simply walk the entire tree until we reach a depth greater than the current
// best min then stop because it cant be down there anymore
//
// Note denoms need to be in reverse order.. max to min!
std::vector<uint32_t> minCoins_prunedImpl(uint32_t total,
const std::vector<uint32_t>& denom,
uint32_t depth,
uint32_t maxDepth)
{
// found trim point..
if (depth > maxDepth)
{
// terminate this search path
std::vector<uint32_t> res(denom.size()+1,0);
res[denom.size()] = INT_MAX;
return res;
}

std::vector<uint32_t> res = minCoins_greedy(total,denom);

// found loop termination..
if (res[denom.size()] == 1)
return res;

for(int i = 0; i < denom.size(); ++i)
{
if (total >= denom[i])
{
uint32_t newMaxDepth = (maxDepth < depth + res[denom.size()] ) ? maxDepth : (depth + res[denom.size()] );

std::vector<uint32_t> pass = minCoins_prunedImpl(total - denom[i],
denom,
depth+1,
newMaxDepth );

if ((pass[denom.size()]  + 1) < res[denom.size()])
{
res = pass;
++(res[i]);
++(res[denom.size()]);
}
}
}

return res;
}

std::vector<uint32_t> minCoins_pruned(uint32_t total,
const std::vector<uint32_t>& denom)
{
return minCoins_prunedImpl(total,
denom,
0,
INT_MAX);
}

// Ok so we know now that the naive isn't smart, and pruning improves this but
// the approach is still wasting allot of time...  what if approach it as a
// divide and conquer problem
//
// To achieve this we first reformulate the induction slightly
//   v[n] = 1 + v[n - c]
// into
//   v[n] = v[c] + v[n - c]
//
// now we have moved from 1 coin at a time on the left and many on the right to
// a full divide and conquer with many coins on both left and right. Since we are
// now choosing multiple coins at one time we may as well pick all the coins from
// each denomination and then remove it from the list.
//
// Note denoms need to be in reverse order.. max to min!
std::vector<uint32_t> minCoins_divAndConqImpl(uint32_t total,
const uint32_t* denomStart,
const uint32_t* denomEnd)
{
std::size_t denomSize = denomEnd - denomStart;
uint32_t maxCount = total / *denomStart;

std::vector<uint32_t> res(denomSize+1,0);
res[denomSize] = INT_MAX;

if (denomSize == 1)
{
// last case cant search... so just give the only result possible
uint32_t leftTotal = total - (maxCount * *denomStart);

if (leftTotal == 0)
{
res[0] = maxCount;
res[1] = maxCount;
}

return res;
}

uint32_t count = maxCount+1;
{
// first case might be special... no need to check it every time
if (total == (maxCount * *denomStart))
{
res[0] = maxCount;
res[denomSize] = maxCount;
count--;
}
}

while (count > 0)
{
--count;
uint32_t leftTotal = total - (count * *denomStart);

std::vector<uint32_t> sub_res = minCoins_divAndConqImpl(leftTotal,
denomStart + 1,
denomEnd);

if (sub_res[denomSize-1] != INT_MAX and
(sub_res[denomSize - 1] + count) < res[denomSize])
{
res[0] = count;
for (int i = 0; i < denomSize; ++i)  // NOTE the oddness.. because its copying total size as well
res[i+1] = sub_res[i];

res[denomSize] += count;
}
}

return res;
}

std::vector<uint32_t> minCoins_divAndConq(uint32_t total,
const std::vector<uint32_t>& denom)
{
// we are dividing by making the full decision for each coin and then removing it from the list
const uint32_t* denomStart = &(denom[0]);
const uint32_t* denomEnd   = &(denom[denom.size()-1]);
denomEnd += 1;

return minCoins_divAndConqImpl(total,
denomStart,
denomEnd);
}

// ok so the divide and conqueror makes a big difference..  but what if we stop
// looking at this as a recursive problem and look at it from a dynamic
// programming perspective, we will start with the top down approach and simply
// cache the results from the prior recursive calls
//
// Note denoms need to be in reverse order.. max to min!
std::vector<uint32_t>& minCoins_topImpl(uint32_t total,
const std::vector<uint32_t>& denom,
std::vector<std::vector<uint32_t> >& cache)
{
std::vector<uint32_t>& res = cache[total];

if (res[denom.size()] > 1 or total == 0)
{
return res;
}

res[denom.size()] = INT_MAX; // max and over flow the count..

for(int i = 0; i < denom.size(); ++i)
{
if (total >= denom[i])
{
std::vector<uint32_t>& pass = minCoins_topImpl(total - denom[i],
denom,
cache);

if ((pass[denom.size()] + 1) < res[denom.size()])
{
res = pass;
++(res[i]);
++(res[denom.size()]);
}
}
}

return res;
}

std::vector<uint32_t> minCoins_top(uint32_t total,
const std::vector<uint32_t>& denom)
{
// setup memory
std::vector<std::vector<uint32_t> > cache;
cache.resize(total + 1);
for (int i = 0; i < total+1; ++i)
cache[i].resize(denom.size()+1);

return minCoins_topImpl(total, denom, cache);
}

// ok but as always we can reverse the approach and produce a bottom-up
// dynamic programming implementation and save our selves all the call overheads
// since in this problem the tree search is not sparse and every case will be
// visited
//
// Note denoms need to be in reverse order.. max to min!
std::vector<uint32_t> minCoins_botImpl(uint32_t total,
const std::vector<uint32_t>& denom,
std::vector<std::vector<uint32_t> >& cache)
{
// compute
for (int target = 1; target <= total; ++target)
{
cache[target][denom.size()] = INT_MAX; // set count to max and overflowed

for(int i = 0; i < denom.size(); ++i)
{
if (target >= denom[i])
{
uint32_t delta = target - denom[i];

if (cache[delta][denom.size()] + 1 < cache[target][denom.size()])
{
cache[target] = cache[delta];
++(cache[target][i]);
++(cache[target][denom.size()]);
}
}
}
}

return cache[total];
}

std::vector<uint32_t> minCoins_bot(uint32_t total,
const std::vector<uint32_t>& denom)
{
// setup memory
std::vector<std::vector<uint32_t> > cache;
cache.resize(total + 1);
for (int i = 0; i < total+1; ++i)
cache[i].resize(denom.size()+1);

return minCoins_botImpl(total,
denom,
cache);
}

// ok so we can improve the bottom up DP version and shave a bit more time by
// visiting items in the order of current coin count as a result we will create
// only the counts that reach towards the
//
std::vector<uint32_t> minCoins_botUpReach(uint32_t total,
const std::vector<uint32_t>& denom)
{
// we are dividing by making the full decistion for each coin and then removing it from the list
if (total == 0) return std::vector<uint32_t>(denom.size()+1, 0);

// setup memory
std::vector< std::vector<uint32_t> > cache(total + 1, std::vector<uint32_t>(denom.size()+1, 0));
std::list<uint32_t> queue;

queue.push_back(0);
while(not queue.empty())
{
uint32_t curTotal = queue.front();
queue.pop_front();

for(int i = 0; i < denom.size(); ++i)
{
uint32_t newTotal = curTotal + denom[i];

if (newTotal <= total and
cache[newTotal][denom.size()] == 0)
{
// ok its empty
cache[newTotal] = cache[curTotal];
++(cache[newTotal][i]);
++(cache[newTotal][denom.size()]);

if (newTotal == total)
return cache[total];

queue.push_back(newTotal);
}
}
}

// impossible case
cache[0][denom.size()] = INT_MAX;
return cache[0];
}

// over all the results are:
// * the greedy continues to kick butt but can be wrong..  this was expected as it
//   guess and looks at 1 path to the solution
// * recursive and depth pruned implementation work but are awful because they
//   repeat the same work over and over
// * the divide and conquer performs well and bets the dynamic programming
//   implementations when the target n is small...  this was a surprising result to
//   me as the top down implementation effectively tries to exhaust the largest
//   coins first, and does this by calling the cache value mid point..  hence i
//   expected it to bet the divide and conquer, because it does effectively
//   the same with caching
// * the dynamic programming versions work best in the long term they:
//  + are pruning because they use the cache results to effect early termination
//  + effectively implement the divide and conquer version by taking largest
//    coin first and it should be faster then the div/conq because it can use the
//    the cached result mid point and can trim the computations of multiple coins draws
//    with the same value (hence its pointless to DP covert the div/conq version)
//  + The bottom up DP also optimizes further by removing the function call overhead

void test(const char* label,
std::function<std::vector<uint32_t> (uint32_t, const std::vector<uint32_t>&)> func,
uint32_t n,
const std::vector<uint32_t>& denom)
{
auto start = std::chrono::system_clock::now();
std::vector<uint32_t> res = func(n, denom);
auto end = std::chrono::system_clock::now();

std::cout << label << ": result:";
for (int i = 0; i < denom.size(); ++i)
std::cout << denom[i] << "x" << res[i] << " ";
std::cout << " count:" << res[denom.size()] << "\n";

std::cout << " --  time:"
<< std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count()
<< " nSec\n";
}

void testSet(uint32_t n,
const std::initializer_list<uint32_t>& dlist)
{
std::vector<uint32_t> denom(dlist);

std::cout << "\n*** test set for " << n << " *** \n";

test("greedy    ", minCoins_greedy,n, denom);
if (n < 30) test("naive     ", minCoins_naive ,n, denom);
else        std::cout << "skipping naive\n";
if (n < 200) test("pruned    ", minCoins_pruned,n, denom);
else         std::cout << "skipping pruned\n";
if (n < 2000) test("divAndConq", minCoins_divAndConq,n, denom);
else         std::cout << "skipping div and conqurer\n";
test("top       ", minCoins_top   ,n, denom);
test("bot       ", minCoins_bot   ,n, denom);
test("botUpReach", minCoins_botUpReach ,n, denom);
}

int main()
{
// breakers
testSet(0,   {20,15,5,4,1});
testSet(1,   {2});

testSet(23,  {20,15,5,4,1}); // attack greedy
testSet(46,  {20,15,5,4,1}); // attack greedy
testSet(31,  {20,15,5,4,1}); // attack greedy
testSet(43, {20,15,5,4,1}); // attack greedy
testSet(100, {20,15,5,4,1}); // attack bottom up
testSet(1000, {20,15,5,4,1});

testSet(1000, {13,7,1});

testSet(10000, {20,15,5,4,1});

}

The output looks like:
*** test set for 0 ***
greedy    : result:20x0 15x0 5x0 4x0 1x0  count:0
--  time:1852 nSec
naive     : result:20x0 15x0 5x0 4x0 1x0  count:0
--  time:572 nSec
pruned    : result:20x0 15x0 5x0 4x0 1x0  count:0
--  time:987 nSec
divAndConq: result:20x0 15x0 5x0 4x0 1x0  count:0
--  time:443 nSec
top       : result:20x0 15x0 5x0 4x0 1x0  count:0
--  time:3814 nSec
bot       : result:20x0 15x0 5x0 4x0 1x0  count:0
--  time:1658 nSec
botUpReach: result:20x0 15x0 5x0 4x0 1x0  count:0
--  time:329 nSec

*** test set for 1 ***
greedy    : result:2x0  count:2147483647
--  time:548 nSec
naive     : result:2x0  count:2147483647
--  time:388 nSec
pruned    : result:2x0  count:2147483647
--  time:563 nSec
divAndConq: result:2x0  count:2147483647
--  time:420 nSec
top       : result:2x0  count:2147483647
--  time:2380 nSec
bot       : result:2x0  count:2147483647
--  time:1881 nSec
botUpReach: result:2x0  count:2147483647
--  time:3839 nSec

*** test set for 23 ***
greedy    : result:20x1 15x0 5x0 4x0 1x3  count:4
--  time:529 nSec
naive     : result:20x0 15x1 5x0 4x2 1x0  count:3
--  time:5941762 nSec
pruned    : result:20x0 15x1 5x0 4x2 1x0  count:3
--  time:69194 nSec
divAndConq: result:20x0 15x1 5x0 4x2 1x0  count:3
--  time:9601 nSec
top       : result:20x0 15x1 5x0 4x2 1x0  count:3
--  time:26959 nSec
bot       : result:20x0 15x1 5x0 4x2 1x0  count:3
--  time:19781 nSec
botUpReach: result:20x0 15x1 5x0 4x2 1x0  count:3
--  time:14906 nSec

*** test set for 46 ***
greedy    : result:20x2 15x0 5x1 4x0 1x1  count:4
--  time:534 nSec
skipping naive
pruned    : result:20x2 15x0 5x1 4x0 1x1  count:4
--  time:798560 nSec
divAndConq: result:20x2 15x0 5x1 4x0 1x1  count:4
--  time:46203 nSec
top       : result:20x2 15x0 5x1 4x0 1x1  count:4
--  time:56899 nSec
bot       : result:20x2 15x0 5x1 4x0 1x1  count:4
--  time:37923 nSec
botUpReach: result:20x2 15x0 5x1 4x0 1x1  count:4
--  time:32182 nSec

*** test set for 31 ***
greedy    : result:20x1 15x0 5x2 4x0 1x1  count:4
--  time:561 nSec
skipping naive
pruned    : result:20x0 15x2 5x0 4x0 1x1  count:3
--  time:134656 nSec
divAndConq: result:20x0 15x2 5x0 4x0 1x1  count:3
--  time:16872 nSec
top       : result:20x0 15x2 5x0 4x0 1x1  count:3
--  time:38468 nSec
bot       : result:20x0 15x2 5x0 4x0 1x1  count:3
--  time:25553 nSec
botUpReach: result:20x0 15x2 5x0 4x0 1x1  count:3
--  time:19032 nSec

*** test set for 43 ***
greedy    : result:20x2 15x0 5x0 4x0 1x3  count:5
--  time:480 nSec
skipping naive
pruned    : result:20x1 15x1 5x0 4x2 1x0  count:4
--  time:731592 nSec
divAndConq: result:20x1 15x1 5x0 4x2 1x0  count:4
--  time:34070 nSec
top       : result:20x1 15x1 5x0 4x2 1x0  count:4
--  time:54569 nSec
bot       : result:20x1 15x1 5x0 4x2 1x0  count:4
--  time:35912 nSec
botUpReach: result:20x1 15x1 5x0 4x2 1x0  count:4
--  time:30253 nSec

*** test set for 100 ***
greedy    : result:20x5 15x0 5x0 4x0 1x0  count:5
--  time:567 nSec
skipping naive
pruned    : result:20x5 15x0 5x0 4x0 1x0  count:5
--  time:7856557 nSec
divAndConq: result:20x5 15x0 5x0 4x0 1x0  count:5
--  time:371883 nSec
top       : result:20x5 15x0 5x0 4x0 1x0  count:5
--  time:107881 nSec
bot       : result:20x5 15x0 5x0 4x0 1x0  count:5
--  time:79875 nSec
botUpReach: result:20x5 15x0 5x0 4x0 1x0  count:5
--  time:60365 nSec

*** test set for 1000 ***
greedy    : result:20x50 15x0 5x0 4x0 1x0  count:50
--  time:728 nSec
skipping naive
skipping pruned
divAndConq: result:20x50 15x0 5x0 4x0 1x0  count:50
--  time:1654224850 nSec
top       : result:20x50 15x0 5x0 4x0 1x0  count:50
--  time:838802 nSec
bot       : result:20x50 15x0 5x0 4x0 1x0  count:50
--  time:766986 nSec
botUpReach: result:20x50 15x0 5x0 4x0 1x0  count:50
--  time:736739 nSec

*** test set for 1000 ***
greedy    : result:13x76 7x1 1x5  count:82
--  time:651 nSec
skipping naive
skipping pruned
divAndConq: result:13x76 7x1 1x5  count:82
--  time:1220761 nSec
top       : result:13x76 7x1 1x5  count:82
--  time:704132 nSec
bot       : result:13x76 7x1 1x5  count:82
--  time:685573 nSec
botUpReach: result:13x76 7x1 1x5  count:82
--  time:686982 nSec

*** test set for 10000 ***
greedy    : result:20x500 15x0 5x0 4x0 1x0  count:500
--  time:559 nSec
skipping naive
skipping pruned
skipping div and conqurer
top       : result:20x500 15x0 5x0 4x0 1x0  count:500
--  time:8379256 nSec
bot       : result:20x500 15x0 5x0 4x0 1x0  count:500
--  time:7830593 nSec
botUpReach: result:20x500 15x0 5x0 4x0 1x0  count:500
--  time:7763225 nSec