C++ Coding Exercise - Maximum unit to load into a truck given it size

Question

You are assigned to put some amount of boxes onto one truck. You are given a 2D vector of box_types where box_type[0] is the number of a type of box and box_type[1] is the units per box for that type. You are also given an integer value for the truck size, this the maximum boxes you can put in the truck. Return the maximum unit that can be put in a given truck.

Example

input : box_types = {{1, 3}, {2, 2}, {3, 1}} truck_size = 4

output: 8

Explanation:

There are

• 1 box of type 0
• 2 box of type 1
• 3 box of type 2

where 0, 1, 2 is the index of the vector

You can take all the boxes of the first type, second type and one box from the third type

max_unit = (1 * 3) + (2 * 2) + (1 * 1) = 8

Here is my implementation

#include <iostream>
#include <algorithm>
#include <vector>
void sort_boxtypes(std::vector<std::vector<int>> &box_types)
{
 std::sort(
 box_types.begin(), box_types.end(), 
 [](const std::vector<int>& a, const std::vector<int> &b)
 {return a[1] > b[1]; }
 );
}
int maximum_units(std::vector<std::vector<int>> box_types, int truck_size)
{
 sort_boxtypes(box_types);
 int max_unit = 0;
 for(const auto& box_type : box_types)
 {
 truck_size -= box_type[0];
 if(truck_size >= 0)
 max_unit += box_type[0] * box_type[1];
 else
 {
 max_unit += (box_type[0] + truck_size) * box_type[1];
 return max_unit;
 } 
 }
 return max_unit;
}
int main()
{
 std::vector<std::vector<int>> box_types = {{5, 10}, {2, 5}, {4, 7}, {3, 9}};
 int max = maximum_units(box_types, 10);
 std::cout << max << '\n';
 
}

Answer 1

• Names are better then indices. Consider

   struct box_type {
   int amount;
   int capacity;
   };
  

  box.amount seems cleaner that box[0].

• Along the same line, declaring such a structure would let you define

   friend bool box_type::operator <(const box_type& l, const box_type& r) {
   return l.capacity < r.capacity;
   }
  

  and eliminate a lambda, as well as sort_boxtypes function.

• I don't like max_units (it sounds like there are min_units somewhere). Similarly, truck_size is a truck size, a constant; consider a remaining_size or something like that.

• It feels that a truck_size >= 0 comparison shall be done beforehand. Consider

   std::sort(boxes.begin(), boxes.end());
   for (auto box = boxes.rbegin(); box != boxes.rend(); ++box) {
   auto the_load = std::min(box.amount, remaining_size());
   units += box.capacity * box.amount;
   remaining_size -= the_load;
   if (remaining_size == 0) {
   break;
   }
   }
   return units;