CareerCup

I could not solve it in the interview but solved it later. The idea is to find the unit cost of each shop. Then run a loop and fetch the min most unit cost that is affordable; until all the money is exhausted or no shop is affordable.

Code in Golang:

func budgetShopping(n int32, bundleQuantities []int32,
	bundleCosts []int32) int32 {

	var totalItems int32
	var perUnitCost []float32

	for i := 0; i < len(bundleCosts); i++ {
		perUnitCost = append(perUnitCost,
			float32(bundleCosts[i])/float32(bundleQuantities[i]))
	}

	for {

		var curMinUnitCost float32
		t := -1

		for j := 0; j < len(bundleCosts); j++ {
			if n >= bundleCosts[j] {
				if t == -1 {
					curMinUnitCost = perUnitCost[j]
					t = j
				} else {
					if perUnitCost[j] < curMinUnitCost {
						curMinUnitCost = perUnitCost[j]
						t = j
					}
				}
			}
		}

		if t == -1 {
			return totalItems
		}

		totalItems += bundleQuantities[t]
		n -= bundleCosts[t]
	}
}

Something like this would go well,(Java)

private static int calculate(int amount, int[] q, int[] c) {
    int ret = 0;
    int bal = 0;
    for (int i = 0; i < n; i++) {
        int n = amount / c[i];
        int quantity = q[i] * n;
        if (quantity > ret) {
            ret = quantity;
            bal = amount % c[i];
        }
    }
    
    if (ret!=0&&bal!=0) ret+=calculate(bal,q,c);
    
    return ret;
}

public int maxNumberChocolates(int amount, int[] quantities, int[] cost, int n) {
        if(amount <= 0 || n < 0) {
            return 0;
        }
        if(amount < cost[n]) {
            return maxNumberChocolates(amount, quantities, cost, n-1);
        } else {
            return Math.max(
                    maxNumberChocolates(amount - cost[n], quantities, cost, n) + quantities[n],
                    maxNumberChocolates(amount, quantities, cost, n-1));
        }
    }

    public int maxNumberChocolatesDpBottomUp(int amount, int[] quantities, int[] cost, int n) {
        int[][] table = new int[amount+1][quantities.length+1];
        for(int i=0; i <= amount; i++) {

            for(int j=0; j <= quantities.length; j++) {
                if(i == 0 || j == 0) {
                    table[i][j] = 0;
                    continue;
                }

                if(i < cost[j-1]) {
                    table[i][j] = table[i][j-1];
                } else {
                    table[i][j] = Math.max(
                                    table[i-cost[j-1]][j] + quantities[j-1],
                                    table[i][j-1]);
                }
            }
        }
        return table[amount][quantities.length];
    }

public int maxNumberChocolates(int amount, int[] quantities, int[] cost, int n) {
        if(amount <= 0 || n < 0) {
            return 0;
        }
        if(amount < cost[n]) {
            return maxNumberChocolates(amount, quantities, cost, n-1);
        } else {
            return Math.max(
                    maxNumberChocolates(amount - cost[n], quantities, cost, n) + quantities[n],
                    maxNumberChocolates(amount, quantities, cost, n-1));
        }
    }

    public int maxNumberChocolatesDpBottomUp(int amount, int[] quantities, int[] cost, int n) {
        int[][] table = new int[amount+1][quantities.length+1];
        for(int i=0; i <= amount; i++) {

            for(int j=0; j <= quantities.length; j++) {
                if(i == 0 || j == 0) {
                    table[i][j] = 0;
                    continue;
                }

                if(i < cost[j-1]) {
                    table[i][j] = table[i][j-1];
                } else {
                    table[i][j] = Math.max(
                                    table[i-cost[j-1]][j] + quantities[j-1],
                                    table[i][j-1]);
                }
            }
        }
        return table[amount][quantities.length];

}

#include <iostream>
#include <map>
#include <iterator>
#include <vector>

auto  budgetShopping = [] (auto n, auto && bundleQuantities, auto && bundleCosts) {

    uint64_t totalItems{};
    std::map<float, int> minPerUnitCostIndex{};

    for (int i = 0; i < bundleCosts.size(); ++i) {
        auto ratio = float(bundleCosts[i])/float(bundleQuantities[i]);
        minPerUnitCostIndex[ratio] = i;
    }

    for ( auto && pair : minPerUnitCostIndex ) {
        while ( n >= bundleCosts[pair.second] ) {
            totalItems += bundleQuantities[pair.second];
            n -= bundleCosts[pair.second];
        }
    }
    return totalItems;
};


int main() {
    auto result = budgetShopping(11, std::vector<int>{10,9,2}, std::vector<int>{10,3,1} );
    std::cout << result << std::endl;
    return 0;
}