We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I wanted to start doing this to explain how I got the answer. Its not for very good developer but for people like me, who are self thought, and are interested in how to get to the point where this becomes second nature.
Please note the function in the algorithim starts by giving you a vector in C++. Not an array as in other languages, creating a situation where the fuction is "leading you on" to use vectors instead of heaps.
Your first step is to write down the problem and understand how to solve it and and understand the linear steps.
The next step is to then use vector functions and try to stay inside of the same class that you're working in. So you'll implement essentially a an algorithm where you will do the erasing function inside of the vector. Followed by pushing back your original values.
Answer from #2 will be correct for most of these solutions but you will find that a few of them will not past due to a time limit. This is where you should go in Google why erase is so expensive. The goal of this exercise is for you to understand when the erase function is acceptable to be used and when it's not.
The next step that you would try is to use an iterator on your vector and the apply the same results and try to sort the algorithm but instead of using a sort from begin to end you would use an iterator. However you'll find that this fails at compile time. The reason for this is that compilers are specifically built to protect you against using pointers in cases where you're manipulating the vectors through resizing.
At this point I finally concluded that using vectors not the right structure to solve the problem. And some type of heap. From here I started building the heap and the and built the exact same algorithm and it worked and I got out.
Big Picture Engineering Lessons from this task:
The erase function in C++ is not your friend and should only be used in exceptional circumstances.
Learn to identify the best data structure to solve your problem without looking at the function in the code first. See if you can convert to that data structure. You will have a better time with data in the correct structure in this case being a heap.
As a corollary to point2, memorize the data structures most commonly used so you don’t have to ask chatgpt for it during the job interview.
int cookies(int k, std::vector A) {
std::priority_queue, std::greater> minHeap(A.begin(), A.end());
int sumvalue = 0;
while (minHeap.top() < k) {
if (minHeap.size() < 2) {
std::cerr << "Error: Not enough elements in vector A to perform operations." << std::endl;
return -1;
}
sumvalue++;
// Extract the two smallest elements
int first = minHeap.top();
minHeap.pop();
int second = minHeap.top();
minHeap.pop();
// Create the new element and add it back to the heap
int newElement = first + 2 * second;
minHeap.push(newElement);
}
return sumvalue;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Jesse and Cookies
You are viewing a single comment's thread. Return to all comments →
I wanted to start doing this to explain how I got the answer. Its not for very good developer but for people like me, who are self thought, and are interested in how to get to the point where this becomes second nature.
Please note the function in the algorithim starts by giving you a vector in C++. Not an array as in other languages, creating a situation where the fuction is "leading you on" to use vectors instead of heaps.
Big Picture Engineering Lessons from this task:
int cookies(int k, std::vector A) { std::priority_queue, std::greater> minHeap(A.begin(), A.end()); int sumvalue = 0;
}