Greedy bug hunt

Questions 1 to 5 of 8

1. 1. The function should return the most units a truck can carry. The input is five boxes of type A (3 units each) and one box of type B (10 units each), with a truck size of 5. It returns 15 instead of 22. What is the bug? ``cpp int maxUnits(std::vector<BoxType> types, int truckSize) { std::ranges::sort(types, std::greater{}, &BoxType::boxes); int total = 0; for (const BoxType& t : types) { int take = std::min(t.boxes, truckSize); total += take * t.unitsPerBox; truckSize -= take; } return total; } ``

   The loop adds the number of boxes instead of the unitsThe sort key is the number of boxes, so the type with the most boxes is taken first instead of the type with the most units per boxThe truck size is never reduced after each typeThe function takes types by value, so the sort has no effect
2. 2. What does this program print? ``cpp #include <cstddef> #include <iostream> #include <vector> std::size_t cheapest_buggy(const std::vector<int>& prices) { std::size_t best = 0; for (std::size_t i = 1; i < prices.size(); ++i) { if (prices[i] <= prices[best]) best = i; } return best; } std::size_t cheapest_fixed(const std::vector<int>& prices) { std::size_t best = 0; for (std::size_t i = 1; i < prices.size(); ++i) { if (prices[i] < prices[best]) best = i; } return best; } int main() { std::vector<int> prices = {6, 3, 9, 3, 3}; std::cout << "buggy " << cheapest_buggy(prices) << " fixed " << cheapest_fixed(prices) << '\n'; } ``

   buggy 1 fixed 1buggy 3 fixed 1buggy 4 fixed 4buggy 4 fixed 1
3. 3. The comment says this function returns the earliest index when prices tie. For prices 4, 2, 7, 2, 9 it returns 3. What is the bug? ``cpp std::size_t cheapest(const std::vector<int>& prices) { std::size_t best = 0; for (std::size_t i = 1; i < prices.size(); ++i) { if (prices[i] <= prices[best]) best = i; } return best; } ``

   The loop starts at index 1 instead of index 0The variable best is never updated when a price is lowerThe comparison is <=, so a later tie replaces the earlier bestThe function returns the price instead of the index
4. 4. Which test input is best at exposing the tie bug in cheapest?

   {4, 1, 1}{4, 1, 9}{9, 8, 7}{1, 2, 3}
5. 5. The problem says a pair fits when the total is at most the limit. For people of weight 1 and 2 with limit 3, it returns 2 boats instead of 1. What is the bug? ``cpp int boats(std::vector<int> people, int limit) { std::ranges::sort(people); int lo = 0; int hi = static_cast<int>(people.size()) - 1; int count = 0; while (lo <= hi) { if (people[lo] + people[hi] < limit) ++lo; --hi; ++count; } return count; } ``

   The sort is in the wrong direction, so the heaviest person is paired firstThe count goes up only when a pair fitsThe variable hi moves down by two when a pair fitsThe test uses <, so a pair whose total equals the limit is rejected