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;
}
// compute the greedy answer..
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
No comments:
Post a Comment