Fruit Basket Packing - Google Top Interview Questions
Problem Statement :
You are given a two-dimensional list of integers fruits.
Each fruits[i] contains [cost, size, total], meaning that fruit i costs cost each, each one has size of size, and there are total of total of them.
You're also given k number of fruit baskets of capacity capacity.
You want to fill the fruit baskets with the following constraints in this order:
Each basket can only contain fruits of the same kind
Each basket should be as full as possible
Each basket should be as cheap as possible
Return the minimum cost required to fill as many baskets as possible.
Constraints
n ≤ 100,000 where n is the length of fruits
0 ≤ k, capacity < 2 ** 31
Example 1
Input
fruits = [
[4, 2, 3],
[5, 3, 2],
[1, 3, 2]
]
k = 2
capacity = 4
Output
9
Explanation
We use two fruit 0s since it makes the first basket as full as possible for total size of 4, which costs 8.
Then, we use one of fruit 2 even though packing fruit 1 would make it just as full because it's also
cheaper. This costs 1 unit.
Solution :
Solution in C++ :
int solve(vector<vector<int>>& fruits, int k, int cap) {
// Points to consider:
// x -> remaining capacity of bucket after filling the i'th fruit
// 1. x = (cap % size) if(size * total < cap) x = cap - (total*size)
// value of x should be minimum -> as we want to fill the basket as full as possible
// 2. cost per unit size should be minimum
multiset<tuple<int, double, vector<int>>> mul;
for (auto v : fruits) {
double cost = v[0];
double size = v[1];
double costratio = (cost / size);
int rem = cap % v[1];
if (v[1] * v[2] < cap) rem = cap - (v[1] * v[2]);
if (v[1] <= cap) mul.insert({rem, costratio, v});
}
int ans = 0;
while (!mul.empty() && k > 0) {
auto [rem, costratio, v] = *mul.begin();
mul.erase(mul.begin());
int fieb = min(v[2], (int)(cap / v[1])); // fruit in each basket
int bf = min(k, (int)(v[2] / fieb)); // baskets filled
ans += fieb * bf * v[0]; // cost of adding the 'fieb' fruits to 'bf' baskets
v[2] -= fieb * bf; // remaining number of current fruits
k -= bf; // remaining baskets
int r = cap % v[1];
if (v[1] * v[2] < cap) r = cap - (v[1] * v[2]);
if (v[2] > 0)
mul.insert({r, costratio,
v}); // Inserting the remaining fruits of this kind into the multiset
}
return ans;
}
Solution in Java :
import java.util.*;
class Solution {
class BasketItem {
public int cost, cap, idx, canTake;
BasketItem(int cost, int cap, int idx, int canTake) {
this.cost = cost;
this.cap = cap;
this.idx = idx;
this.canTake = canTake;
}
}
public int solve(int[][] fruits, int k, int capacity) {
PriorityQueue<BasketItem> pq =
new PriorityQueue<BasketItem>((BasketItem a, BasketItem b) -> {
if (a.cap != b.cap)
return b.cap - a.cap; // big cap first
return a.cost - b.cost; // small cost second
});
for (int i = 0; i < fruits.length; i++) {
int take = Math.min((int) Math.floor(capacity / fruits[i][1]), fruits[i][2]);
if (take > 0) {
int canTake = (int) Math.floor(fruits[i][2] / take);
BasketItem item =
new BasketItem(take * fruits[i][0], take * fruits[i][1], i, canTake);
pq.add(item);
fruits[i][2] -= canTake * take;
}
}
int ans = 0;
while (k > 0 && !pq.isEmpty()) {
BasketItem topItem = pq.remove();
if (topItem.canTake >= k) {
ans += k * topItem.cost;
k = 0;
break;
} else {
ans += topItem.canTake * topItem.cost;
k -= topItem.canTake;
}
int i = topItem.idx;
int take = Math.min((int) Math.floor(capacity / fruits[i][1]), fruits[i][2]);
if (take > 0) {
int canTake = (int) Math.floor(fruits[i][2] / take);
BasketItem item =
new BasketItem(take * fruits[i][0], take * fruits[i][1], i, canTake);
pq.add(item);
fruits[i][2] -= canTake * take;
}
}
return ans;
}
}
Solution in Python :
class Solution:
def solve(self, fruits, k, size):
baskets = []
for fruit_cost, fruit_size, fruit_count in fruits:
if fruit_size > size:
continue
full_basket_count = size // fruit_size
full_baskets = 0 if not full_basket_count else fruit_count // full_basket_count
full_basket_size = full_basket_count * fruit_size
if full_basket_count:
baskets.append((full_basket_size, full_basket_count * fruit_cost, full_baskets))
rest_basket_count = fruit_count - full_baskets * full_basket_count
rest_basket_size = rest_basket_count * fruit_size
if rest_basket_count:
baskets.append((rest_basket_size, rest_basket_count * fruit_cost, 1))
total_cost = 0
for _basket_size, basket_cost, baskets_available in sorted(
baskets, key=lambda b: (-b[0], b[1])
):
if k == 0:
break
baskets_used = min(k, baskets_available)
total_cost += baskets_used * basket_cost
k -= baskets_used
return total_cost
View More Similar Problems
Merging Communities
People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w
View Solution →Components in a graph
There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu
View Solution →Kundu and Tree
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that
View Solution →Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →No Prefix Set
There is a given list of strings where each string contains only lowercase letters from a - j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked. Note If two strings are identical, they are prefixes of each other. Function Descriptio
View Solution →