## Numeric Interview Question for Backend Developers

Country: United States

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

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

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

Comment hidden because of low score. Click to expand.
0

The greedy algorithm you've provided is not always optimal - can you think of a case where it fails?

This is the classic "knapsack" problem, which is solved by dynamic programing.

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

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

Comment hidden because of low score. Click to expand.
0

Is this an optimal solution?

Comment hidden because of low score. Click to expand.
0

its an (n log(n)) solution assumes 2 things
1 need to use up all the money
2 can come back to the beginning of the shops if there is a balance of money

but to my knowledge this might be the optimal solution

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

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

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

``````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];``````

}

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

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

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

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.

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

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

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