C++ Educational Content Creator | 20 years of Software Engineering experience distilled into digestible daily posts
Sunday C++ interview problem. Given an array of integers and the size of a sliding window, calculate the maximum for each of the positions of the sliding window. The solution should run in O(n). Solve it yourself: https://lnkd.in/esF-uBT2 Solution: https://lnkd.in/eX9RnQJ6 #cpp #cplusplus #coding #programming #dailybiteofcpp
I got result in recursive mode with clean and simple code. Please review my solution: #include <iostream> #include <vector> #include <algorithm> using namespace std; void max(std::vector<int> v,unsigned int k ) { if(v.size()<k) return; cout<<*max_element(v.begin(), v.begin()+k); v.erase(begin(v)); max(v,k); } int main() { vector<int> s{1,3,-1,4,-3,5,3,6,7,-1,8}; max(s,3); return 0; }
You add numbers until you reach the window size, once the window size is reached you store the sum (of the numbers in the window) in max variable (result so far). Then, for every number going out of the window gets subtracted to prep the next sub array (that will make up the next window) and every next number becomes part of the subarray and max is updated if it is greater than the previous max. In the end the max should have the result.
Here is my take on that problem (problem #3 in the text): https://blog.pramp.com/coding-interviews-and-the-snake-game-have-this-one-thing-in-common-e0189fba1c9c
Maybe I'm wrong, but isn't the naive solution also O(n)? It isn't very good in the real world, but it certainly looks to be O(n). We iterate n - k + 1 times in order to move the sliding window. In each iteration, we find the maximum value inside the window (e.g. call max_element on the window). This will do k comparisons. So we have O(k (n - k + 1)) = O(nk - k² + k) = O(nk) = O(n)