Sliding windows

Questions 1 to 5 of 9

1. 1. Predict the output of this program. ``cpp #include <cstddef> #include <iostream> #include <vector> using namespace std; int main() { vector<int> v = {2, -1, 4, -3, 5, 1, 0}; size_t k = 3; int sum = 0; for (size_t i = 0; i < k; ++i) { sum += v[i]; } cout << sum; for (size_t right = k; right < v.size(); ++right) { sum += v[right]; sum -= v[right - k]; cout << " " << sum; } cout << "\n"; } `` What does it print?

   5 -1 6 3 65 0 6 35 0 6 3 65 0 6 3 0
2. 2. The function below returns the length of the shortest run of values whose sum is at least the target. What does this program print? ``cpp #include <cstddef> #include <iostream> #include <vector> using namespace std; size_t shortest_run_at_least(const vector<long long>& values, long long target) { size_t best = values.size() + 1; long long sum = 0; size_t left = 0; for (size_t right = 0; right < values.size(); ++right) { sum += values[right]; while (sum >= target) { size_t length = right - left + 1; if (length < best) best = length; sum -= values[left]; ++left; } } return best == values.size() + 1 ? 0 : best; } int main() { vector<long long> v = {3, 4, 1, 5, 2, 6, 1}; cout << shortest_run_at_least(v, 10) << "\n"; } ``

   2345
3. 3. The function below returns the length of the longest run whose sum is at most the limit. What does this program print? ``cpp #include <cstddef> #include <iostream> #include <vector> using namespace std; size_t longest_run_at_most(const vector<long long>& values, long long limit) { size_t best = 0; long long sum = 0; size_t left = 0; for (size_t right = 0; right < values.size(); ++right) { sum += values[right]; while (sum > limit) { sum -= values[left]; ++left; } size_t length = right - left + 1; if (length > best) best = length; } return best; } int main() { vector<long long> v = {1, 2, 1, 1, 3, 1, 1}; cout << longest_run_at_most(v, 4) << "\n"; } ``

   3245
4. 4. The loop below should track the sum of the last k values as the window slides. On its first step it reads memory outside the vector. Which change fixes it? ``cpp #include <cstddef> #include <iostream> #include <vector> using namespace std; int main() { vector<int> v = {4, 1, 5, 2}; size_t k = 2; int sum = 0; for (size_t right = 0; right < v.size(); ++right) { sum += v[right]; sum -= v[right - k]; cout << sum << "\n"; } } ``

   Change k to an int, so that right - k can go below zeroDelete the sum -= line, because the window only ever growsSum the first k values before the loop, then start right at kPrint the sum before the add, so the first window is skipped
5. 5. This function should return the length of the shortest run whose sum is at least the target. It returns 0 for every input. Why? ``cpp #include <cstddef> #include <iostream> #include <vector> using namespace std; size_t shortest_run_at_least(const vector<long long>& values, long long target) { size_t best = 0; long long sum = 0; size_t left = 0; for (size_t right = 0; right < values.size(); ++right) { sum += values[right]; while (sum >= target) { size_t length = right - left + 1; if (length < best) best = length; sum -= values[left]; ++left; } } return best; } ``

   The while loop never shrinks the window, so left stays at 0best starts at 0, and no length is smaller than 0, so best never changesThe return line should be best + 1 to count the last valuesum is a long long, so it cannot be compared with target