Since last time I have been looking a bit at Dynamic Programming (DP) and in particular combinatorial optimization problems, for example the Knapsack Problem and the Change-making problem. For those of you that are interested in learning more about DP check out GeeksforGeeks resources on DP. Here you will find reading material plus a LOT of different practice problems.
I was recently faced with two codility tasks when applying for a job as an Embedded Software Engineer. For those of you who arn't familiar with Codility you can check out their website here: www.codility.com Task one - Dominator The first task was called Dominator. The goal was to, given a std::vector of integers, find an integer that occurs in more than half of the positions in the vector. If no dominator was found -1 should be returned. My approach was to loop through the vector from the first to the last element, using a std::map to count the number of occurences of each integer. If the count ever reached above half the size of the vector I stopped and returned that integer and if I reached the end without finding a dominator I returned -1. So was that a good approach? Well, the reviewer at the company rated the solution as 'pretty ok'. His preferred solution was store the first integer in the array and set a counter to 1. Then loop through the remaining i
Kommentarer
Skicka en kommentar