Cookies and candy

Questions 1 to 5 of 7

1. 1. What does this program print? ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <utility> #include <vector> using Match = std::pair<int, int>; std::vector<Match> assignCookies(std::vector<int> greed, std::vector<int> cookies) { std::sort(greed.begin(), greed.end()); std::sort(cookies.begin(), cookies.end()); std::vector<Match> matches; std::size_t cookie = 0; for (int need : greed) { while (cookie < cookies.size() && cookies[cookie] < need) { ++cookie; } if (cookie == cookies.size()) { break; } matches.emplace_back(need, cookies[cookie]); ++cookie; } return matches; } int main() { for (auto [need, size] : assignCookies({5, 3, 1}, {4, 3, 2, 1})) { std::cout << need << "->" << size << ' '; } std::cout << '\n'; } `` Choose the exact output, including the spaces between numbers.

   1->1 3->21->11->1 3->33->3 1->1
2. 2. What does this program print? ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <vector> std::vector<int> candyCounts(const std::vector<int>& ratings) { const std::size_t n = ratings.size(); std::vector<int> candy(n, 1); if (n == 0) { return candy; } for (std::size_t i = 1; i < n; ++i) { if (ratings[i] > ratings[i - 1]) { candy[i] = candy[i - 1] + 1; } } for (std::size_t i = n - 1; i > 0; --i) { if (ratings[i - 1] > ratings[i]) { candy[i - 1] = std::max(candy[i - 1], candy[i] + 1); } } return candy; } int main() { for (int c : candyCounts({1, 2, 2, 1})) std::cout << c << ' '; std::cout << '\n'; } `` Choose the exact output, including the spaces between numbers.

   1 2 1 12 2 1 11 2 2 21 2 2 1
3. 3. After the sort, how many steps does the cookie walk take for n children and m cookies?

   About n plus m steps, with each child and each cookie looked at about onceAbout n times m steps, a check of every pairAbout n log n steps, because the walk also sortsAbout n squared steps, because the cookie index moves back
4. 4. Why does the second pass of the candy method use std::max instead of a plain assignment?

   Because std::max is faster than a plain assignmentBecause it keeps the larger value, so a value set by the first pass is never loweredBecause every child must end with the same number of candiesBecause the ratings vector must be sorted first
5. 5. What is the bug in this function? ``cpp std::vector<Match> assignCookies(std::vector<int> greed, std::vector<int> cookies) { std::sort(greed.begin(), greed.end()); std::sort(cookies.begin(), cookies.end()); std::vector<Match> matches; std::size_t cookie = 0; for (int need : greed) { while (cookie < cookies.size() && cookies[cookie] < need) { ++cookie; } matches.emplace_back(need, cookies[cookie]); ++cookie; } return matches; } ``

   The children are sorted in the wrong directionThe cookie index is never reset to 0 for the next childThere is no check for cookie == cookies.size(), so cookies[cookie] reads past the end when the cookies run outstd::size_t cannot hold the value of need